Posted on 2014-01-18 17:36
Uriel 閱讀(136)
評論(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 };