Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Validate Binary Search Tree-2014.01.18

Posted on 2014-01-18 17:36 Uriel 阅读(111) 评论(0)  编辑 收藏 引用 所属分类: LeetCode
判断一棵树是否是BST,也就是DFS到每个节点判断其左子树节点是否都小于根节点,右子树节点是否都大于根节点,DFS的时候记录左右界

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool res;
13     bool DFS(TreeNode *root, int l, int r) {
14         if(root == NULL) return true;
15         else
16             return root->val > l && root->val < r && DFS(root->left, l, root->val) && DFS(root->right, root->val, r);
17     }
18     bool isValidBST(TreeNode *root) {
19         return DFS(root, -1000000, 1000000);
20     }
21 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理