1.6 Reverse binary tree upside down

Assumption: Given tree is not null

Input: TreeNode root

Output: TreeNode reversed tree, not the original tree

Corner case: if root.left = null, return root

Solution:

1. Look at nodes 1(root), 2, 3, and think about how to reverse these three

2. At current level, we need to:

root.left.left = root.right

root.left.right = root

root.left = null

root.right = null

https://www.geeksforgeeks.org/flip-binary-tree/

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