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.
这道题应该在Recover Binary Search Tree之前做。
中序遍历，记得保存前一个节点。只要pre->val>=root->val就错了。
1 class Solution { 2 public: 3 bool isValidBST(TreeNode *root) { 4 pre = NULL; 5 return inorder(root); 6 } 7 8 bool inorder(TreeNode *root) { 9 if (!root) return true; 10 if (!inorder(root->left)) return false; 11 if (pre && pre->val >= root->val) return false; 12 pre = root; 13 return inorder(root->right); 14 } 15 private: 16 TreeNode* pre; 17 };
用Morris Traversal的方式竟然报runtime error。同样的代码可以跑在本机上，修改一下也可以通过Recover Binary Search Tree。真是奇怪。难道是leetccode上这道题不允许修改树本身。
1 class Solution { 2 public: 3 bool isValidBST(TreeNode *root) { 4 TreeNode* pre = NULL; 5 TreeNode* current = root; 6 7 while (current != NULL) { 8 if (current->left == NULL) { 9 if (pre != NULL && pre->val >= current->val) return false; 10 pre = current; 11 current = current->right; 12 } else { 13 TreeNode* rightmost = current->left; 14 while (rightmost->right != NULL && rightmost->right != current) rightmost = rightmost->right; 15 if (rightmost->right == NULL) { 16 rightmost->right = current; 17 current = current->left; 18 } else { 19 rightmost->right = NULL; 20 if (pre != NULL && pre->val >= current->val) return false; 21 pre = current; 22 current = current->right; 23 } 24 } 25 } 26 return true; 27 } 28 };
Leetcode | Validate Binary Search Tree,布布扣,bubuko.com
Leetcode | Validate Binary Search Tree
原文：http://www.cnblogs.com/linyx/p/3732089.html