二叉树创建 & 遍历

参考：Python --- 二叉树的层序建立

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = None
        self.right = None

def creatTree(nodeList):
    if nodeList[0] == None:  return None
    head = TreeNode(nodeList[0])
    nodes = [head] # 用于存放树中的节点，每生成一个节点就将其放入该列表中，此处将根节点存入。
    j = 1  # 创建变量j用于nodeList中元素的索引，初始为1.因为第0个元素已经创建根节点了。
    for node in nodes:  # 依次取出Nodes列表中的节点，对其创建左子节点和右子节点
        if node != None:
            node.left = (TreeNode(nodeList[j])) if nodeList[j] != None else None
            nodes.append(node.left) # 将新建的节点加入Nodes数组，使其在for循环中可以继续为其添加子节点
            j += 1
            if j == len(nodeList): # 如果与nodeList值相等说明全部节点已经添加完毕了，直接返回head根节点就完成了树的建立
                return head
            
            node.right = (TreeNode(nodeList[j])) if nodeList[j] != None else None
            j += 1
            nodes.append(node.right)
            if j == len(nodeList):
                return head
a = [1,2,3,4,None,6,7]
a = creatTree(a)

# 使用：返回二叉树最长路径，Leecode 124
class Solution:
    def __init__(self):
        self.maxSum = float("-inf")
    def maxPathSum(self, root: TreeNode) -> int:
        def maxGain(node):
            if not node:
                return 0
            leftGain = max(maxGain(node.left), 0)
            rightGain = max(maxGain(node.right), 0)
         
            priceNewpath = node.val + leftGain + rightGain

            self.maxSum = max(self.maxSum, priceNewpath)
            return node.val + max(leftGain, rightGain)
        maxGain(root)
        return self.maxSum

s = Solution()
s.maxPathSum(a)

Continue......