python iterative post order traversal


  • 0
    P

    Hi All,

    I couldn't find an iterative python solution ANYWHERE in the web. I thought I'd share mine and your comments and feedback will make it better. Feel free to post your own version.

    The approach is to use post order traversal as a bottom up approach. We're building the height starting from the leaves. We're updating the parent's left and right height from the children's height. This leads me to constantly iterate through the stack. I don't think this is the best approach. Feedback for better approach is welcome :)

    # 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 diameterOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            
            if not root:
                return 0
                
            stack = [[root, False, "", 0, 0]]
            diameter = 0
            
            while stack:
                node, visited, parent, left_height, right_height = stack.pop()
                
                if visited:
                    #update stack
                    for i, row in enumerate(stack):
                        
                        parent_node = row[0]
                        parent_visited = row[1]
                        parent_parent = row[2]
                        parent_left_height = row[3]
                        parent_right_height = row[4]
                        
                        #if (parent == parent_node) and (node is not root): #if node's parent
                        if parent == parent_node:
                            
                            #update left height or right height
                            if parent_node.left == node:
                                parent_left_height = max(parent_left_height, max(left_height,right_height) + 1)
                                stack[i] = [parent_node, parent_visited, parent_parent, parent_left_height, parent_right_height]
                            if parent_node.right == node:
                                parent_right_height = max(parent_right_height, max(left_height, right_height) + 1)
                                stack[i] = [parent_node, parent_visited, parent_parent, parent_left_height, parent_right_height]
                            print parent_left_height, parent_right_height
                            #print "1", parent_node.left.val
                    
                    diameter = max(diameter, left_height + right_height)
                else:
                    stack.append([node, True, parent, left_height, right_height])
                    if node.right: stack.append([node.right, False, node, left_height, right_height])
                    if node.left: stack.append([node.left, False, node, left_height, right_height ])
                    
            return diameter
    

Log in to reply
 

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