首页 > 代码库 > Leetcode | Validate Binary Search Tree
Leetcode | Validate Binary Search Tree
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 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。