首页 > 代码库 > Validate Binary Search Tree(DFS)

Validate Binary Search Tree(DFS)

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node‘s key.
  • The right subtree of a node contains only nodes with keys greater than the node‘s key.
  • Both the left and right subtrees must also be binary search trees.

描述:即判断一棵树是不是二叉搜索树(左孩子小于父节点值,右孩子大于父亲节点值,且其左子树和右子树也同时满足BST)

思路:双层递归。

第一层,递归每一个节点是否满足,左边所有节点都小于它,右边所有节点都大于它。

第二层,如何来实现判断,左边所有节点都小于根,右边所有节点大于根。(每个节点都要作为根)。

特殊:root为空时,return true

代码:

class Solution {public:    bool isLeftValid(TreeNode *root,int val){//某个根的左树,val该根的值        if(root==NULL)             return true;        return root->val<val&&isLeftValid(root->left,val)&&isLeftValid(root->right,val);    }    bool isRightValid(TreeNode *root,int val){//某个根的右树,val该根的值        if(root==NULL)             return true;        return root->val>val&&isRightValid(root->left,val)&&isRightValid(root->right,val);    }    bool isValidBST(TreeNode *root) {        if(root==NULL)             return true;        bool flag=isLeftValid(root->left,root->val)&&isRightValid(root->right,root->val);        if(!flag)            return false;        return isValidBST(root->left)&&isValidBST(root->right);    }};

 

Validate Binary Search Tree(DFS)