[关闭]
@markheng 2018-04-10T13:52:55.000000Z 字数 1306 阅读 1674

验证二叉搜索树 Validate Binary Search Tree LeetCode

算法


搜索二叉树验证

二叉搜索树的判断需要借助中序遍历,中序遍历的序列需要是递增的才是二叉搜索树。因此有递归和递归方法的非递归形式,以及一种Morris遍历的方法。前两种方法都是O(n)的空间,Morris遍历是O(1)的方法。

递归解法

递归中用全局变量记录前驱指针

  1. bool isValidBST(TreeNode* root) {
  2. isValid(root);
  3. return isValided;
  4. }
  5. bool isValided = true;
  6. TreeNode* pre = NULL;
  7. void isValid(TreeNode* cur)
  8. {
  9. if(!cur || !isValided) return;
  10. isValid(cur->left);
  11. if(!pre){
  12. pre = cur;
  13. }else{
  14. if(pre -> val >= cur -> val)
  15. {
  16. isValided = false;
  17. }
  18. pre = cur;
  19. }
  20. isValid(cur->right);
  21. }

栈解法

栈中节点作为当前节点,与前驱节点作比较

  1. void isValidBST(TreeNode* root)
  2. {
  3. vector<TreeNode*> vec;
  4. TreeNode *p = root, *pre = NULL;
  5. while(p || !vec.empty())
  6. {
  7. while(p)
  8. {
  9. vec.push_back(p);
  10. p = p -> left;
  11. }
  12. TreeNode* t = vec.back(); vec.pop_back();
  13. if(pre && t -> val <= pre->val) return false;
  14. pre = t;
  15. p = t -> right;
  16. }
  17. return true;
  18. }

Morris中序遍历

Morris中序遍历是一种空间复杂度为O(1)的方法,只用到了cur和pre两个指针,cur指针指向当前节点,pre指向中序遍历顺序的前驱节点。

这个解法在

      5
     / \
    1   10
       /
      4

这种情况本地没问题,但是oj下会出现runtime error,不知道为什么。

  1. bool isValidBST(TreeNode* root) {
  2. if(root == NULL) return true;
  3. TreeNode *cur = root, *pre = NULL, *parent = NULL;
  4. while(cur)
  5. {
  6. if(!cur -> left)
  7. {
  8. if(parent && parent->val >= cur->val) return false;
  9. parent = cur;
  10. cur = cur -> right;
  11. }else{
  12. pre = cur->left;
  13. while(pre->right && pre->right != cur )
  14. pre = pre->right;
  15. if(!pre->right)
  16. {
  17. pre->right = cur;
  18. cur = cur -> left;
  19. }else{
  20. pre -> right = NULL;
  21. if(pre->val >= cur->val) return false;
  22. parent = cur;
  23. cur = cur -> right;
  24. }
  25. }
  26. }
  27. return true;
  28. }

参考:http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注