LeetCode题目:Recover Binary Search Tree

By | 2012 年 10 月 16 日

分析
题目说在一棵二叉搜索树中有两个节点位置错了,要在常数空间将其改正。
想到的算法就是中序遍历二叉树,找到这一对错误的节点,之后交换它们的值。
如何找到这一对节点呢?
这一对节点先出现的那个肯定是比其中序后继大的,后出现的那个节点的后继,肯定不大于先出现这个错误节点的值。
但是中序遍历二叉树的空间复杂度是O(logN)啊,如何做到常数,目前还没想到。

<br>
Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.



代码:368ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode *root) {
        vector trace;
        TreeNode *cur = root;
        //find the lest node in the BST
        while(cur->left) {
            trace.push_back(cur);
            cur = cur->left;
        }
        TreeNode *wrong0 = NULL;//first wrong node
        TreeNode *wrong1 = NULL;//last wrong node
        while(true){
            TreeNode *next = NULL;
            //find the next inorder node
            if(cur->right){
                //if cur have right child, the next inorder node is the most left node in this sub-tree
                trace.push_back(cur);
                next = cur->right;
                while(next->left){
                    trace.push_back(next);
                    next = next->left;
                }
                if(!wrong0 && cur->val > next->val) {
                    wrong0 = cur;
                } else if(wrong0 && wrong0->val <= next->val) {
                    wrong1 = cur;
                    break;
                }
                cur = next;
            } else {
                //if cur have no right child, the next inorder nodt is the most near parant which cur belong to it's left sub-tree
                TreeNode *tempCur = cur;
                while(trace.size()) {
                    TreeNode *tempPar = trace.back();
                    if(tempPar->left == tempCur) {
                        next = tempPar;
                        break;
                    }
                    tempCur = tempPar;
                    trace.pop_back();
                }
                if(next) {
                    if(!wrong0 && cur->val > next->val) {
                        wrong0 = cur;
                    } else if(wrong0 && wrong0->val <= next->val) {
                        wrong1 = cur;
                        break;
                    }
                    cur = next;
                }
            }
            if(!next) break;
        }
        if(!wrong1) wrong1 = cur;
        int temp = wrong0->val;
        wrong0->val = wrong1->val;
        wrong1->val = temp;
    }
};



Code rewrite at 2013-1-18, 388ms pass large set, more clear

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == root) return;
        TreeNode *firstNode = NULL, *secondNode = NULL;
        
        //find first node, with inorder traversal
        stack trace;
        if(root) trace.push(root);
        bool forward = true;
        TreeNode *pre = NULL;
        TreeNode *lastNode = NULL;
        while(trace.size()) {
            TreeNode *cur = trace.top();
            if(forward) {
                if(cur->left && cur->left != pre) {
                    trace.push(cur->left);
                } else {
                    forward = false;
                }
            } else {
                if(pre != cur->right) {
                    if(lastNode && lastNode->val > cur->val) {
                        firstNode = lastNode;
                        break;
                    }
                    lastNode = cur;
                }
                if(cur->right && cur->right != pre) {
                    trace.push(cur->right);
                    forward = true;
                } else {
                    trace.pop();
                }
            }
            pre = cur;
        }
        if(NULL == firstNode) return;
        
        //find second node, in reverse order of inorder traversal
        while(trace.size()) trace.pop();
        if(root) trace.push(root);
        forward = true;
        pre = NULL;
        lastNode = NULL;
        while(trace.size()) {
            TreeNode *cur = trace.top();
            if(forward) {
                if(cur->right && cur->right != pre) {
                    trace.push(cur->right);
                } else {
                    forward = false;
                }
            } else {
                if(pre != cur->left) {
                    if(lastNode && lastNode->val < cur->val) {
                        secondNode = lastNode;
                        break;
                    }
                    lastNode = cur;
                }
                if(cur->left && cur->left != pre) {
                    trace.push(cur->left);
                    forward = true;
                } else {
                    trace.pop();
                }
            }
            pre = cur;
        }
        if(NULL == secondNode) return;
        
        //swap
        int t = firstNode->val;
        firstNode->val = secondNode->val;
        secondNode->val = t;
        
    }
};

3 thoughts on “LeetCode题目:Recover Binary Search Tree

  1. nandawys

    递归方法 中序遍历二叉树 空间复杂度应该是O(n)
    这道题难道是让用非递归的方法遍历吗……

    Reply
    1. uniEagle Post author

      是平均logN,最坏N。不知道这题怎么做到常数空间。我的代码就是非递归,但是本质上没有改善空间复杂度。

      Reply
      1. aad
        /**
         * Definition for binary tree
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
         */
        public class Solution {
            ArrayList t;
            TreeNode previous;
            public void recoverTree(TreeNode root) {
                // Start typing your Java solution below
                // DO NOT write main() function
                t = new ArrayList();
                previous=null;
                inorder(root);
                int temp = t.get(0).val;
                t.get(0).val = t.get(t.size()-1).val;
                t.get(t.size()-1).val = temp;
            }
            public void inorder(TreeNode root) {
                if(root==null) return;
                inorder(root.left);
                if(previous!=null&&previous.val>root.val) {
                    if(!t.contains(previous)) t.add(previous);
                    if(!t.contains(root)) t.add(root);
                }
                previous = root;
                inorder(root.right);
            }
        }
        
        Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注