Binary Trees Depth first: return a value up
345. Invert Binary Tree
You are given root, the root node of a binary tree. Invert the tree and return its root.
A binary tree is made of nodes. Each node holds a value and has at most two children, a left child and a right child. To invert a tree, swap the left and right child of every node. The result is the mirror image of the tree: what was on the left is now on the right, at every level.
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out. The output shows the tree you return the same way.
Example 1
Input: root = [10, 4, 15, null, 7, 12]
[10,15,4,null,12,7]Explanation: Every node swaps its two children. The root's children 4 and 15 change places. 7 was the right child of 4 and is now its left child, and 12 moves from the left of 15 to its right.
Example 2
Input: root = []
[]Explanation: An empty tree has nothing to swap, so the answer is the empty tree.
Example 3
Input: root = [-3, -3, null, 0]
[-3,null,-3,null,0]Explanation: Each node has only a left child, and each of those children moves to the right. A path down the left side becomes a path down the right side.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
Clarifying questions
What you would ask an interviewer before writing any code.