Binary Tree Upside Down

Problem: Binary Tree Upside Down

During the depth-first search, left child and right child of current node are previously decided. So we can link node to new left and right children and do dfs on node's old left child and pass in node's old right child and node itself as parameters.

Code in Python:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def upsideDownBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root: return root
        def dfs(node, left, right):
            _left = node.left
            _right = node.right
            node.left, node.right = left, right
            if _left: return dfs(_left, _right, node)
            else: return node
        return dfs(root, None, None)