# Super easy preOrderTraversal Solution in Python

• ``````# 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

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