Simple Post Order Traversal Solution.


  • 0
    Y
        def maxPathSum(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            # Not assuming there are no negetives.
            # One stack post order traversal.
            stack = []
            current = root
            dic = {}
            self.za_best = -float('inf')
            while True:
                while current:
                    stack.append(current)
                    current = current.left
                if not stack:
                    break
                leftiest = stack[-1]
                if not leftiest.right:
                    visit = leftiest
                    self.visiting(visit, dic)
                    stack.pop()  # pop out the 'leftiest' node.
                    while stack and stack[-1].right == visit:
                        visit = stack[-1]
                        self.visiting(visit, dic)
                        stack.pop()
                else:
                    current = leftiest.right
            return self.za_best
        
        def visiting(self, node, dic):
            if node.left and node.right:
                left_best_path_val = dic[node.left]
                right_best_path_val = dic[node.right]
                both_left_and_right = left_best_path_val + right_best_path_val + node.val # This value cannot be used by other nodes.
                self.za_best = max(self.za_best, both_left_and_right)
                best_straight = max(left_best_path_val+node.val, right_best_path_val + node.val, node.val)
                self.za_best = max(self.za_best, best_straight)
                dic[node] = best_straight
            elif node.left:
                left_best_path_val = dic[node.left]
                best_straight = max(left_best_path_val+node.val, node.val)
                self.za_best = max(self.za_best, best_straight)
                dic[node] = best_straight
            elif node.right:
                right_best_path_val = dic[node.right]
                best_straight = max(right_best_path_val + node.val, node.val)
                self.za_best = max(self.za_best, best_straight)
                dic[node] = best_straight
            else:
                # Is leaf.
                dic[node] = node.val
                self.za_best = max(self.za_best, node.val)
    

Log in to reply
 

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