Super easy preOrderTraversal Solution in Python


  • 0
    Y
    # 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 maxPathSum(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def preOrderTraversal(node):
                if not node:
                    return None, None
                
                (left_max_sum, left_max_sum_edge) = preOrderTraversal(node.left)
                (right_max_sum, right_max_sum_edge) = preOrderTraversal(node.right)
                
                max_len_through_node = 0
                if left_max_sum_edge > 0:
                    max_len_through_node += left_max_sum_edge
                if right_max_sum_edge > 0:
                    max_len_through_node += right_max_sum_edge 
                max_len_through_node += node.val
                
                max_node_edge = 0
                if left_max_sum_edge > 0 or right_max_sum_edge > 0:
                    max_node_edge = max(left_max_sum_edge, right_max_sum_edge) 
                max_node_edge += node.val
                
                return max(max_len_through_node, left_max_sum, right_max_sum), max_node_edge
                
            return preOrderTraversal(root)[0]
    

    max_len_through_node is the maximal path length through the current node
    left_max_sum is the maximal path length in left sub tree
    right_max_sum is the maximal path length in right sub tree
    max_node_edge is the possible maximal path length starting from node to any offspring node.

    For root, we compare the maximal path length through node, only in left tree and in right tree, return the maximal


Log in to reply
 

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