层次创建

参考：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)

前序+中序遍历构造二叉树

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder: return None
        root = preorder[0]
        tree = TreeNode(root)
        rootPos = inorder.index(root)

        inLeft = inorder[: rootPos]
        inRight = inorder[rootPos+1 :]
        preLeft = preorder[1 : len(inLeft)+1]
        preRight = preorder[len(inLeft)+1 :]

        tree.left = self.buildTree(preLeft, inLeft)
        tree.right = self.buildTree(preRight, inRight)
        
        return tree

中序遍历

参考：中序遍历

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

#——————————————or————————————#
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(node):
            if not node:
                return []
            
            dfs(node.left)
            res.append(node.val)
            dfs(node.right)
            return res
        return dfs(root)

迭代

# 参考：https://leetcode.cn/problems/binary-tree-inorder-traversal/solution/jian-dan-yi-dong-javac-pythonjs-er-cha-s-w80i/
def inorderTraversal1(self, root: TreeNode) -> List[int]:
    if not root:
        return []
    res, stack = list(), list()
    curr = root
    while curr or len(stack):
        while curr:
            stack.append(curr)
            curr = curr.left
        node = stack.pop()
        res.append(node.val)
        curr = node.right
    return res


#----------------or-----------------#
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node is None: continue
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

层次遍历

迭代

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def LevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        stack = []
        q = [root]
        while q:
            tmp = []
            #node = q.pop()
            n = len(q)
            for _ in range(n):
                node = q.pop(0)
                tmp.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)

            stack.append(tmp[:])
            
        return stack

Continue......