Recover Binary Search Tree, Leetcode 解题笔记

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?

先看O(n) space的情况,涉及到BST的错误,肯定是比较大小。这里应该立刻反应出树的in order traversal是有序遍历,所以只要中序遍历一遍并找出其中排序错误的地方即可。
具体实现中要利用一个lastNode来记录上次遍历的节点,以利于比较当前节点和上个遍历到的节点的大小。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode lastNode;
    TreeNode first;
    TreeNode second;
    public void recoverTree(TreeNode root) {
        lastNode = new TreeNode(Integer.MIN_VALUE);
        inorder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
    public void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.left);
        if(root.val < lastNode.val && first == null){
            first = lastNode;
        }
        if(root.val < lastNode.val && first != null){
            second = root;
        }
        lastNode = root;
        inorder(root.right);
    }
}

如果按照题目的进一步要求,只能用O(1) space呢,这里就要使用一种高端大气上档次的算法了:Morris Traversal!
具体算法可参考这里:http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html

以中序遍历为例:
步骤:

1. 如果当前节点的左孩子为空,则输出当前节点并将其右孩子作为当前节点。

2. 如果当前节点的左孩子不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点(左子树中的最右下的节点)。

a) 如果前驱节点的右孩子为空,将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。

b) 如果前驱节点的右孩子为当前节点,将它的右孩子重新设为空(恢复树的形状)。输出当前节点。当前节点更新为当前节点的右孩子。

3. 重复以上1、2直到当前节点为空。

14214057-7cc645706e7741e3b5ed62b320000354

void inorderMorrisTraversal(TreeNode *root) {
    TreeNode *cur = root, *prev = NULL;
    while (cur != NULL)
    {
        if (cur->left == NULL)          // 1.
        {
            printf("%d ", cur->val);
            cur = cur->right;
        }
        else
        {
            // find predecessor
            prev = cur->left;
            while (prev->right != NULL && prev->right != cur)
                prev = prev->right;

            if (prev->right == NULL)   // 2.a)
            {
                prev->right = cur;
                cur = cur->left;
            }
            else                       // 2.b)
            {
                prev->right = NULL;
                printf("%d ", cur->val);
                cur = cur->right;
            }
        }
    }
}

所以最优解如下:

public class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode current = root;
        TreeNode prev = null;
        TreeNode node1 = null;
        TreeNode node2 = null;
        while (current != null) {
            if (current.left == null) {
                if (prev != null) {
                    if (prev.val >= current.val) {
                        if (node1 == null)
                            node1 = prev;
                        node2 = current;
                    }
                }
                prev = current;
                current = current.right;
            } else {
                TreeNode t = current.left;
                while (t.right != null && t.right != current)
                    t = t.right;
                if (t.right == null) {
                    t.right = current;
                    current = current.left;
                } else {
                    t.right = null;
                    if (prev != null) {
                        if (prev.val >= current.val) {
                            if (node1 == null)
                                node1 = prev;
                            node2 = current;
                        }
                    }
                    prev = current;
                    current = current.right;
                }
            }
        }
        int tmp = node1.val;
        node1.val = node2.val;
        node2.val = tmp;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s