Python Iterative and Recursive Solution


  • 0
    A

    Implement a stack based post order traversal and store intermediate results in dictionaries.
    You can also delete the results of node.left and node.right as and when you postorder process the node in question since this means that the entire subtree rooted at node is traversed.
    PS: There's probably some unnecessary stuff going on in this.

    # 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 maxDepthAndPathLen(self, node):
            max_depth = max_right = max_left = 0
            max_path = max_path_left = max_path_right = 0
            
            if node.left:
                max_left, max_path_left = self.maxDepthAndPathLen(node.left)
            else:
                max_left = -1
            
            if node.right:
                max_right, max_path_right = self.maxDepthAndPathLen(node.right)
            else:
                max_right = -1
            
            if not node.left and not node.right:
                return 0, 0
            
            max_depth = max(max_left, max_right) + 1
            max_path = max(max_left + max_right + 2, max_path_left, max_path_right)
            return max_depth, max_path
        
        def diameterOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            
            node_stack = [root]
            max_depth = {}
            max_path = {}
            seen = set()
            #max_final = -1
            while node_stack:
                node = node_stack.pop()
    
                if node not in seen:
                    seen.add(node)
                    node_stack.append(node)
                    
                    if node.left:
                        node_stack.append(node.left)
                    if node.right:
                        node_stack.append(node.right)
                else:
                    if not node.left and not node.right:
                        max_depth[node] = 0
                        max_path[node] = 0
                    elif not node.left and node.right:
                        max_right = max_depth[node.right]
                        max_depth[node] = max_right + 1
                        max_path_right = max_path[node.right]
                        max_path[node] = max(max_depth[node], max_path_right)
                        
                    elif node.left and not node.right:
                        max_left = max_depth[node.left]
                        max_depth[node] = max_left + 1
                        max_path_left = max_path[node.left]
                        max_path[node] = max(max_depth[node], max_path_left)
                        
                    else:
                        max_left = max_depth[node.left]
                        max_right = max_depth[node.right]
                        max_depth[node] = max(max_left, max_right) + 1
                        max_path[node] = max(max_left + max_right + 2, 
                                             max_path[node.left], 
                                             max_path[node.right])
                                             
                        
            return max_path[root]
            
    

Log in to reply
 

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