LeetCode "99. Recover Binary Search Tree"

first thought

It’s similar to valid BST, using DFS to find the two invalid nodes and save them to a list.

solution

class Solution {
    public void recoverTree(TreeNode root) {
        List<TreeNode> mistake = new ArrayList<>();
        this.dfs(root, mistake, Integer.MIN_VALUE, Integer.MAX_VALUE);
        if (mistake.size() == 2) {
            TreeNode m1 = mistake.get(0);
            TreeNode m2 = mistake.get(1);
            int temp = m1.val;
            m1.val = m2.val;
            m2.val = temp;
        }
        return;
    }
    private void dfs(TreeNode root, List<TreeNode> mistake, int min, int max) {
        if (root == null) {
            return;
        }
        if (root.left != null && (root.left.val < min || root.left.val > root.val)) {
            mistake.add(root.left);
        }
        if (root.right != null && (root.right.val > max || root.right.val < root.val)) {
            mistake.add(root.right);
        }
        if (mistake.size() == 2) {
            return;
        }
        this.dfs(root.left, mistake, min, root.val);
        this.dfs(root.right, mistake, root.val, max);
    }
}

problem

WA.

reason

Haven’t considered the invalid two nodes are one node and it’s child. In this case, the solution may only find one node.

modification

Save parent node to the list. If there’s only two nodes, it represents the mistakes are parent and it’s child, then swap them. If there’s four nodes, then swap the two children.

class Solution {
    public void recoverTree(TreeNode root) {
        List<TreeNode> mistake = new ArrayList<>();
        this.dfs(root, mistake, Integer.MIN_VALUE, Integer.MAX_VALUE);
        if (mistake.size() == 2) {
            TreeNode m1 = mistake.get(0);
            TreeNode m2 = mistake.get(1);
            int temp = m1.val;
            m1.val = m2.val;
            m2.val = temp;
        } else if (mistake.size() == 4) {
            TreeNode m1 = mistake.get(1);
            TreeNode m2 = mistake.get(3);
            int temp = m1.val;
            m1.val = m2.val;
            m2.val = temp;
        }
        return;
    }
    private void dfs(TreeNode root, List<TreeNode> mistake, int min, int max) {
        if (root == null) {
            return;
        }
        if (root.left != null && (root.left.val < min || root.left.val > root.val)) {
            mistake.add(root);
            mistake.add(root.left);
        }
        if (root.right != null && (root.right.val > max || root.right.val < root.val)) {
            mistake.add(root);
            mistake.add(root.right);
        }
        if (mistake.size() == 2) {
            return;
        }
        this.dfs(root.left, mistake, min, root.val);
        this.dfs(root.right, mistake, root.val, max);
    }
}

problem

Still WA. And what’s more, recursion uses non-constant space.

reason

Maybe is the handle of the min and max.

此处用到了 Morris Traversal，一个特别好的不用多余空间（包括栈跟递归）的遍历二叉树的方法，此处先说一下这个方法。

Morris Traversal

主要思想

遍历树的关键就是怎么确定下一个遍历的节点，递归是通过特性来保证在访问某个节点的时候能够提前把它的所有子节点的遍历写出来，从而不用人为的特意保存该节点（感官上来说，其实考虑递归底层实现的话还是会有整个函数体的压栈跟出栈，保存的不仅仅是这个节点了，而是整个函数）；栈就是人为的主动保存该节点以及在合适的时候弹出该节点；而 Morris Traversal 则是利用树本身的一些特点来保存确定下个节点，以BST的中序遍历举例（相对简单，方便理解）。

先看一个树

中序遍历结果是：[1,2,3,4,5,6,7,8,9]

可以直观的发现（也是树中序遍历的必然结果）每个节点的前驱最右叶子节点即是中序遍历的前一个数字（根是6的时候前驱叶子是5，根是4的时候是3），可以根据这个特性来保存每个节点。因为是叶子节点，所以可以利用上叶子节点的右孩子来保存其下一个节点，当遍历到该叶子节点时，通过右孩子自然就会回到曾经的这个根节点上来。所以每个叶子的节点的右孩子都会是中序遍历中它的下一个数字，也是某个祖先节点。

保存方法：

向左遍历
找到当前节点（a）的前驱最右叶子节点（b）
把 b 的右孩子设为当前节点
如果 b 的右孩子为当前节点，说明以a为根的左子树已经遍历完毕，则输出a，往右遍历

如 1，2，3，4，5，6，7，8，9
1->2,3,4,5->6,…
到2的时候发现1右等于2，说明2的左子树遍历完毕，输出2，则目前是1，2
遍历2的右：4
4往左遍历之后是1，2，3->4,5->6
4也结束，现在是1，2，3，4
遍历4的右：5
5左空，右是6，则输出5，现在是1，2，3，4，5
6的前驱右子是5，5的右是6自己，则输出6，并切断5的右子。
往6的右遍历。。。

代码实现

public void inorderMorrisTraversal(TreeNode root) {
  List<Integer> list = new ArrayList<>();
  TreeNode cur = root;
  TreeNode temp = root;
  while (cur != null) {
    if (cur.left != null) {
      temp = cur.left;
      while (temp.right != null) {
        if (temp.right == cur) {
          break;
        }
        temp = temp.right;
      }
      if (temp.right == null) {
        temp.right = cur;
        cur = cur.left;
      } else {
        list.add(cur.val);
        temp.right = null;
        cur = cur.right;
      }
    } else {
      list.add(cur);
      cur = cur.right;
    }
  }
}

modification

根据 Morris Traversal，在遍历过程中缓存相邻两个node，如果前node大于后node，则该node为错误node

class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode first = null;
        TreeNode second = null;
        TreeNode cur = root;
        TreeNode temp = root;
        TreeNode preNode = null;
        while (cur != null) {
            if (cur.left != null) {
                temp = cur.left;
                while (temp.right != null) {
                    if (temp.right == cur) {
                        break;
                    }
                    temp = temp.right;
                }
                if (temp.right == null) {
                    temp.right = cur;
                    cur = cur.left;
                } else {
                    if (preNode == null) {
                        preNode = cur;
                    } else {
                        if (preNode.val > cur.val) {
                            if (first == null) {
                                first = preNode;
                                second = cur;
                            } else {
                                second = cur;
                            }
                        }
                    }
                    preNode = cur;
                    temp.right = null;
                    cur = cur.right;
                }
            } else {
                if (preNode == null) {
                    preNode = cur;
                } else {
                    if (preNode.val > cur.val) {
                        if (first == null) {
                            first = preNode;
                            second = cur;
                        } else {
                            second = cur;
                        }
                    }
                }
                preNode = cur;
                cur = cur.right;
            }
        }
        int tempVal = first.val;
        first.val = second.val;
        second.val = tempVal;
    }
}

阳光夜风