Simple concise solution in python O(n)


  • 1
    Z

    Definition for a binary tree node

    class TreeNode:

    def init(self, x):

    self.val = x

    self.left = None

    self.right = None

    class Solution:

    def postorderTraversal(self, root):
        stack=[]
        output=[]
    
        while True:
            while root:
                stack.append(root)
                root=root.left
            if stack==[]:
                return output
            node=stack[-1]
            if node.right:
                root=node.right
            else:
                output.append(node.val)
                node=stack.pop()
                if stack==[]:
                    return output
                else:
                    if stack[-1].right==node:
                        stack[-1].right=None
                    else:
                        stack[-1].left=None
                root=stack.pop()

Log in to reply
 

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