题解 | # JAVA Morris Traversal二叉搜索树与双向链表# [P3]

要求时间O(1), 那就只能Morris Traversal了。
Morris这个视频讲的挺清楚 https://www.youtube.com/watch?v=wGXB9OWhPTg

只需要以下变化
1. 记录第一个visited node作为ans输出
2. 记录lastVisited node, 也就是当前链表的末尾，visit(cur)时就append cur.

时间 O(1), 空间 O(n)

public class Solution {
    TreeNode lastVisited = null;
  
    public TreeNode Convert(TreeNode pRootOfTree) {
      TreeNode ans = null;
      TreeNode cur = pRootOfTree;
      while (cur != null) {
        if (cur.left == null) {  // visit node if no left child
          // first visited node of inOrderTraversal is the list head
          if (lastVisited == null) ans = cur;
          visit(cur);
          cur = cur.right;
        } else {
          TreeNode pred = findPredecessor(cur);
          if (pred.right == null) {
            pred.right = cur;
            cur = cur.left;
          } else {
            // pred.right == null; 这步可有可无
            visit(cur);
            cur = cur.right;
          }
        }
      }
      return ans;
    }
  
    // Append cur to lastVisited to build list.
    void visit(TreeNode cur) {
      if (lastVisited != null) {
        lastVisited.right = cur;
        cur.left = lastVisited;
      }
      lastVisited = cur;
    }
  
    TreeNode findPredecessor(TreeNode cur) {
      TreeNode n = cur.left;
      while (n.right != null && n.right != cur) 
        n = n.right;
      
      return n;
    }
}