首页 > 代码库 > 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)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。