A python solution bases on non-recursive preorder-traverse


  • 1
    L
    class Solution:
        # @param root, a tree node
        # @return nothing, do it in place
        def flatten(self, root):
            stack = []
            if root:
                p = root
                if root.right:
                    stack.append(root.right)
                if root.left:
                    stack.append(root.left)
                while stack:
                    node = stack.pop()
                    if node.right:
                        stack.append(node.right)
                    if node.left:
                        stack.append(node.left)
                    p.right = node
                    p.left = None
                    p = p.right
    

    As we can see, the node order in linked list is same as preorder traverse.


  • 0
    V

    But maybe you should do it in place.


  • 0
    L

    @Veklip It's in place. But we use extra space.


  • 0
    V

    oops,I used to think of in place as not using extra space.So,what is exactly the way do it in place?I am new to Algorithm.


  • 0
    V
    This post is deleted!

Log in to reply
 

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