Given a binary tree where all the right nodes are leaf nodes, flip it upside down and turn it into a tree with left leaf nodes as the root.

Examples

    1

  /    \

2        5

/ \

3 4

is reversed to

    3

  /    \

2        4

/ \

1 5

Solution: 注意node之间关系，注意返回的是新root，不是原root

wrong: reverse了树，但最后只返回一个root node

  public TreeNode reverse(TreeNode root) {
    if (root == null) {
      return root;
    }
    if (root.left != null) {
      TreeNode left = reverse(root.left);
      left.right = root.right;
      left.left = root;
      root.left = null;
      root.right = null;
    }
    return root;
  }

correct:

  public TreeNode reverse(TreeNode root) {
    if (root == null || root.left == null) {
      return root;
    }
      TreeNode newRoot = reverse(root.left);
      root.left.right = root.right;
      root.left.left = root;
      root.left = null;
      root.right = null;
      return newRoot;
  }