Transfer of Tree

Invert Binary Tree

1. 调换左右子树，然后返回当前节点。

public TreeNode invertTree(TreeNode root) {
     if (root == null) {
         return null;
     }
     TreeNode temp = invertTree(root.left);
     root.left = invertTree(root.right);
     root.right = temp;
     return root;
}

BST to greater Sum Tree

public TreeNode Transfer(TreeNode root) {
    int[] preSum = {0};
    helper(root, preSum);
    return root;
}
private void helper(TreeNode root, int[] preRoot) {
    if(root == null) return;
    helper(root.right, preRoot);
    preRoot[0] += root.val;
    root.val = preRoot[0];
    helper(root.left, preRoot);
}

Binary Tree Upside Down

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;
 }

Populating Next Right Pointers in Each Node I and II

public void connect(TreeLinkNode root) {
     if (root == null) return;
     if (root.left != null) {
         root.left.next = root.right;
         if (root.next != null)
             root.right.next = root.next.left;
     }
     connect(root.left);
     connect(root.right);
 }

Flatten Binary Tree to Linked List

This problem is very helpful to understand postOrder traversal of tree. When we traversal tree fromright -> left -> root we need record root of every subtree. If we get previous root that means current left subtree.

// straightforward: O(NlogN)??
public void flatten(TreeNode root) {
    if (root == null) return;

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

    TreeNode temp = root.right;
    root.right = root.left;
    root.left = null;

    while (root.right != null) {
        root = root.right;
    }
    root.right = temp;
}
// postOrder : O(N)
public void flatten(TreeNode root) {
    flatten(root,null);
}
private TreeNode flatten(TreeNode root, TreeNode pre) {
    if(root==null) return pre;
    pre=flatten(root.right,pre);    
    pre=flatten(root.left,pre);
    root.right=pre;
    root.left=null;
    pre=root;
    return pre;
}

Construct Binary Tree from Preorder and Inorder Traversal

private int inIndex=0, preIndex=0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
    return helper(preorder, inorder, Integer.MAX_VALUE);
}
private TreeNode helper(int[] preorder, int[] inorder, int target) {
    if (inIndex >= inorder.length || inorder[inIndex] == target) {
        return null;
    }
    TreeNode root = new TreeNode(preorder[preIndex]);
    preIndex++;
    root.left = helper(preorder, inorder, root.val);
    inIndex++;
    root.right = helper(preorder, inorder, target);
    return root;
}

Construct Binary Tree from Inorder and Postorder Traversal

• 本题最重要的点是要搞清楚下次循环的index，左右边界是什么
• 所有的边界都是按照距离来算的。从 index 在inorder 里面 距离inLeft 的距离来推到pre, post 中的下次循环
• distance = (k - inLeft)

• Inorder:

  • Left -> (preLeft + 1, preLeft + distance)
  • Right ->(preLeft + distance + 1, preRight)

• PostOrder:

  • Left -> (postLeft, postLeft + distance - 1)
  • Right ->(posLeft + distance, postRight - 1)

Example:
                  1

              2       3

            4   5   6    7

Inorder:    4 - 2 - 5 - 1 - 6 - 3 - 7 // 两种重构都是按照Inorder 的顺序来排，这里可以看出左右子树
Preorder:   1 - 2 - 4 - 5 - 3 - 6 - 7
PostOrder:  4 - 5 - 2 - 1 - 6 - 3 - 7

Next:
Inorder: 
    root: 1
    Left SubTree: 4,2,5
    Right SubTree: 3,6,7
PosterOrder:
    root: 1
    Left SubTree: 4,5,2
    Right SubTree: 6,3,7

public TreeNode buildTree(int[] preorder, int[] inorder) { 
    return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); 
} 
private TreeNode helper(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) { 
    if (preLeft > preRight || inLeft > inRight) return null; 
    TreeNode cur = new TreeNode(preorder[preLeft]); 
    int index = 0; 
    for (int i = inLeft; i <= inRight; i++) { 
        if (inorder[i] == preorder[preLeft]) { 
            index = i; 
            break;         
        } 
    } 
    cur.left = helper(preorder, preLeft + 1, preLeft + (index - inLeft), inorder, inLeft, index - 1); 
    cur.right = helper(preorder, preLeft + (index - inLeft) + 1, preRight, inorder, index + 1, inRight); 
    return cur; 
}

Serialize and Deserialize Binary Tree