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.
解法1:min/max法
这是我觉得最直接了当、简洁易懂的方法:
1. 先top-down递归,由父节点来传递子节点的值所允许的范围minVal < x->val < maxVal。如果该条件不符合,返回false。
2. 如果上述条件符合,只说明当前节点x本身符合BST条件。还需要bottom-up递归来检查当前节点的左右子树是否也都符合BST条件。左子树的取值范围为(minVal, x->val),右子树取值范围为(x->val, maxVal)。
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: bool isValidBST(TreeNode *root) { return validateBST(root, INT_MIN, INT_MAX); } bool validateBST(TreeNode *root, int minVal, int maxVal) { if(!root) return true; if(root->val<=minVal || root->val>=maxVal) return false; return validateBST(root->left, minVal, root->val) && validateBST(root->right, root->val, maxVal); } }; |
解法2:inorder traversal法
1. 对一个BST进行inorder traverse,必然会得到一个严格单调递增序列,否则则是invalid BST。
2. Inorder traverse时并不需要记录下整个访问过的序列,而只需要保存前一个访问的节点数值就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public: bool isValidBST(TreeNode *root) { int curMax = INT_MIN; return validateBST(root, curMax); } bool validateBST(TreeNode *root, int &curMax) { if(!root) return true; if(!validateBST(root->left, curMax)) return false; if(curMax >= root->val) return false; curMax = root->val; return validateBST(root->right, curMax); } }; |
ln 10:检验左子树是否valid,并通过引用得到左子树的最大值curMax。
ln 11-12:在左子树valid的情况下,判断当前节点是否大于curMax。在当前节点也valid的情况下,更新curMax为当前节点。
ln 13:当左子树和当前节点都valid时,返回右子树的检验结果即可。
第一种解法不能通过root 就是int_max 的 test case,branch left 过刚比较max, branch right 过就比较min可以过
ReplyDeletehttp://fisherlei.blogspot.com/2013/01/leetcode-validate-binary-search-tree.html
大家好 我是一个兔子
ReplyDelete第二种解法貌似不能通过 input 仅为 INT_MIN的情况
ReplyDelete要把 curMax 类型设为 long 并且初始化为 INT_MIN - 1