Posted on 2014-01-18 17:36
Uriel 阅读(112)
评论(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 };