114. Flatten Binary Tree to Linked List

很符合递归思想的写法，美中不足是每次都要把左子树遍历一遍好去找尾端节点，如果整个树左子树体积非常大而右子树很小的话，时间复杂度会很高。最差的情况是，整个树是一个只有左边的链表，时间复杂度可以达到 O(n^2)，而且用递归还要花费栈空间。

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;

        flatten(root.left);
        flatten(root.right);

        TreeNode left = root.left;
        TreeNode right = root.right;

        root.left = null;
        root.right = left;
        while(root.right != null) {
            root = root.right;
        }
        root.right = right;
    }
}

于是这题有特别赞的O(n)时间O(1)空间写法，还是利用 Morris 遍历。

Morris 遍历的特点是寻找左子树中能沿着右边走最长的节点，并且利用这个节点做文章；这题是把 right 指针直接指向 root 的右节点了，相当于每次缩进去【root.left -> 左子树最长向右路径】这段到右子树上，如此反复。因此省去了最坏情况下重复遍历寻找链表尾的过程。

public class Solution {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while(cur != null){
            if(cur.left == null){
                cur = cur.right;
            } else {
                TreeNode prev = cur.left;
                while(prev.right != null){
                    prev = prev.right;
                }
                prev.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
        }
    }
}

156. Binary Tree Upside Down / Binary Tree Flipping

操作方法如图。

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null || root.left == null) return root;
        TreeNode newRoot = upsideDownBinaryTree(root.left);

        root.left.left = root.right;
        root.left.right = root;
        root.left = null;
        root.right = null;

        return newRoot;
    }
}