题目描述：
给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:
输入: [1,2,3]

   1
  / \
 2   3

输出: 6

示例 2:
输入: [-10,9,20,null,null,15,7]

-10
/
9 20
/
15 7

输出: 42

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

思路：1、递归思想计算最大值（max=左支最大+右支最大）。
2、层序遍历每个节点，计算以这个节点为中心的最长路径，从中选取最大的作为最终结果。

代码：

import tree


class Solution(tree.Tree):
    
    def maxPathSum(self,root):
        MQ=[]
        node=root
        MQ.append(node)
        self.MAX=-9999999
        while MQ:
            node=MQ.pop(0)
            self.digui(node)
            if self.max_>self.MAX:
                self.MAX=self.max_
            if node.lchild:
                MQ.append(node.lchild)
            if node.rchild:
                MQ.append(node.rchild)
        
        return self.MAX
    def digui(self,root):
        if root==None:
            return 0
        left=max(self.digui(root.lchild),0)
        right=max(self.digui(root.rchild),0)
        
        if root.e==None:
            root.e=0
        self.max_=root.e+left+right
        return root.e+max(left,right)
        
        


if __name__=='__main__':
    treenode=[-10,9,20,None,None,15,7]
    T=tree.Tree()
    for i in treenode:
        T.add(i)

    path=Solution().maxPathSum(T.root)
    print("二叉树的最大路径和为："+str(path))

运行结果：
二叉树的最大路径和为：42

树结构的实现：

class Node(object):
    def __init__(self,e=None,lchild=None,rchild=None):
        self.e=e
        self.lchild=lchild
        self.rchild=rchild

#树类
class Tree(object):
    def __init__(self,root=Node(None,None,None)):
        self.root=root
        self.height=0
        self.MyQueue=[]
    
    #按层序添加节点到树中
    def add(self,e):
        node=Node(e)
        
        if self.root.e==None:
            self.root=node
            if not node==None:
                self.height+=1
                
            self.MyQueue.append(self.root)
        else:
            treeNode=self.MyQueue[0]
            if treeNode.lchild==None:
                treeNode.lchild=node
                if not node==None:
                    self.height+=1
                    
                self.MyQueue.append(treeNode.lchild)
            else:
                treeNode.rchild=node
                
                self.MyQueue.append(treeNode.rchild)
                self.MyQueue.pop(0)
            
    
    #层序遍历
    def level(self):
        if self.root==None:
            return
        MQ=[]
        node=self.root
        MQ.append(node)
        while MQ:
            node=MQ.pop(0)
            print(node.e)
            if node.lchild:
                MQ.append(node.lchild)
            if node.rchild:
                MQ.append(node.rchild)
                
    #前序遍历
    def front(self,root):
        if root==None:
            return
        print(root.e)
        self.front(root.lchild)
        self.front(root.rchild)
    
    #中序遍历
    def middle(self,root):
        if root==None:
            return
        self.middle(root.lchild)
        print(root.e)
        self.middle(root.rchild)
        
      #后序遍历
    def post(self,root):
        if root==None:
            return
        self.post(root.lchild)
        self.post(root.rchild)   
        print(root.e)