https://leetcode.com/problems/binary-tree-upside-down/
Binary Tree Upside Down
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:
Given a binary tree {1,2,3,4,5}
,
1 / \ 2 3 / \ 4 5
return the root of the binary tree [4,5,2,#,#,3,1]
.
4 / \ 5 2 / \ 3 1
confused what "{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:
1 / \ 2 3 / 4 \ 5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}"
.
class Solution: # @param root, a tree node # @return root of the upside down tree def upsideDownBinaryTree(self, root): # take care of the empty case if not root: return root # take care of the root l = root.left r = root.right root.left = None root.right = None # update the left and the right children, form the new tree, update root while l: newL = l.left newR = l.right l.left = r l.right = root root = l l = newL r = newR return root
Now, the basic idea is to go though from the original root (7), make root’s left child (1) as new parent whose left child will be the original root’s right left (6) and right child will be the original root (7). After that, you set new root to root.left (1), and process it in the same way. As pointed out by (https://leetcode.com/discuss/18410/easy-o-n-iteration-solution-java), the core idea is to “Just think about how you can save the tree information you need before changing the tree structure“.
Reference
https://leetcode.com/discuss/30902/iteration-python-solution
https://leetcode.com/discuss/18410/easy-o-n-iteration-solution-java