Python, recursive solution

  • 0

    Here is my (non-trivial, old-fashioned) solution. Obviously, from the first sight, I can use DFS to traverse the tree. I like to do DFS recursively. I do use a stack to keep track of the val in nodes, but I could have used a queue instead. When making the flatten tree, I again use a recursive approach.

    ## push the node vals in a stack, with right-most in the bottom, post-order traversal fashion
    def pushNodesInStack(root, stack):
        if (root == None):
            return stack
        if not root.right == None:
            stack = pushNodesInStack(root.right, stack)
        if not root.left == None:
            stack = pushNodesInStack(root.left, stack)
        return stack
    ## recursively set the right val all the way up to root
    def setRight(root, stack):
        if len(stack) == 0:
            return None
        root.left = None
        root.val = stack.pop()
        root.right = setRight(TreeNode(0), stack)
        return root
    class Solution(object):
        def flatten(self, root):
            stack = []
            pushNodesInStack(root, stack)
            root = setRight(root, stack)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.