二叉树

2026-02-02

1. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

输入：root = [3,9,20,null,null,15,7]
输出：3

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        else:
            return max(1+self.maxDepth(root.left), 1+self.maxDepth(root.right))

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        res = 0
        def depth(node, cont):
            if node is None:
                return
            else:
                cont+=1
            nonlocal res
            res = max(res,cont)
            depth(node.left,cont)
            depth(node.right, cont)
        depth(root,0)
        return res

2. 相同的树

（100）给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

输入：p = [1,2,3], q = [1,2,3]
输出：true

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p == q
        else:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

3. 对称二叉树

（101）给你一个二叉树的根节点 root ，检查它是否轴对称。

输入：root = [1,2,2,3,4,4,3]
输出：true

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.issametric(root.left,root.right)
    def issametric(self, left, right):
        if left is None or right is None:
            return left == right
        return left.val == right.val and self.issametric(left.left,right.right) and self.issametric(left.right, right.left)

4. 平衡二叉树

给定一个二叉树，判断它是否是平衡二叉树。平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。

输入：root = [3,9,20,null,null,15,7]
输出：true

# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        return self.height(root) != -1
    def height(self, node):
        if node is None:
            return 0
        left_height = self.height(node.left)
        if left_height == -1:
            return -1
        right_height = self.height(node.right)
        if right_height == -1 or abs(right_height - left_height) >1:
            return -1
        return max(left_height, right_height) +1

5. 二叉树的右视图

（199）给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def de(node, depth):
            if node is None:
                return
            if depth == len(res):
                res.append(node.val)
            de(node.right, depth+1)
            de(node.left, depth+1)
        de(root,0)
        return res