python iterative post order traversal

  • 0

    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)
                    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.