CodeTop - 二叉树

二叉树的层序遍历

解题要点

使用deque双端队列里面的popleft来模仿队列
层序遍历的时候，要记录当前层的数量为固定数
注意空树的情况，提前排除

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 如果二叉树为空，直接返回空列表
        if not root:
            return []
        else:
            # 初始化队列，将根节点加入队列
            queue = deque([root])
        
        # 用于存储最终结果的二维列表
        result = []
        
        # 当队列不为空时，继续遍历
        while len(queue) > 0:
            # 存储当前层的节点值
            level = []
            # 当前层的节点数量
            level_len = len(queue)
            
            # 遍历当前层的所有节点
            for _ in range(level_len):
                # 从队列中取出一个节点
                node = queue.popleft()
                
                # 如果当前节点有左子节点，将左子节点加入队列
                if node.left:
                    queue.append(node.left)
                # 如果当前节点有右子节点，将右子节点加入队列
                if node.right:
                    queue.append(node.right)
                
                # 将当前节点的值加入当前层的列表
                level.append(node.val)
            
            # 将当前层的节点值列表加入最终结果
            result.append(level)
        
        # 返回最终的层序遍历结果
        return result

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(m)，其中 m 是二叉树中某一层的最大节点数。队列最多存储一层的节点。

二叉树的最近公共祖先

236. 二叉树的最近公共祖先

解题要点

递归思想：从根节点开始递归，分别在左子树和右子树中查找节点 p 和 q。
终止条件：
- 如果当前节点为空，返回 None。
- 如果当前节点是 p 或 q，直接返回当前节点。
合并条件：
- 如果左子树和右子树都找到了目标节点，说明当前节点就是最近公共祖先。
- 如果只有左子树找到了目标节点，返回左子树的结果。
- 如果只有右子树找到了目标节点，返回右子树的结果。
边界条件：如果树为空，直接返回 None。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def lowestCommonAncestor(self, root, p, q) -> 'TreeNode':
        # 如果当前节点为空，或者当前节点是p或q，直接返回当前节点
        if not root or root == p or root == q:
            return root
      
        # 递归在左子树中查找p和q
        left = self.lowestCommonAncestor(root.left, p, q)
        # 递归在右子树中查找p和q
        right = self.lowestCommonAncestor(root.right, p, q)
      
        # 如果左子树和右子树都找到了p和q，说明当前节点是最近公共祖先
        if left and right:
            return root
        # 如果只有左子树找到了p或q，返回左子树的结果
        elif left:
            return left
        # 如果只有右子树找到了p或q，返回右子树的结果
        elif right:
            return right
        # 否则返回None
        else:
            return None

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点最多被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归调用的栈深度取决于树的高度，最坏情况下空间复杂度为 O(n)（树退化为单链表时）。

二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历

解题要点

层序遍历：使用队列实现二叉树的层序遍历。
锯齿形遍历：使用标志位right_to_left控制每一层的遍历方向：
- right_to_left = False：从左到右遍历，顺序添加到结果中。
- right_to_left = True：从右到左遍历，需要将当前层的节点值反转后再添加到结果中。
反转操作：通过level.reverse()实现当前层节点值的反转。
边界条件：如果树为空，直接返回空列表。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 如果树为空，直接返回空列表
        if not root:
            return []
        else:
            # 初始化队列，将根节点加入队列
            queue = deque([root])
      
        # 标志位，用于控制遍历方向
        right_to_left = False
        # 存储最终结果的二维列表
        result = []
      
        # 当队列不为空时，继续遍历
        while len(queue) > 0:
            # 存储当前层的节点值
            level = []
            # 当前层的节点数量
            level_len = len(queue)
          
            # 遍历当前层的所有节点
            for _ in range(level_len):
                # 从队列中取出一个节点
                node = queue.popleft()
              
                # 如果当前节点有左子节点，将左子节点加入队列
                if node.left:
                    queue.append(node.left)
                # 如果当前节点有右子节点，将右子节点加入队列
                if node.right:
                    queue.append(node.right)
              
                # 将当前节点的值加入当前层的列表
                level.append(node.val)
          
            # 如果当前层需要从右到左遍历，反转当前层的节点值列表
            if right_to_left:
                level.reverse()
          
            # 将当前层的节点值列表加入最终结果
            result.append(level)
            # 切换遍历方向
            right_to_left = not right_to_left
      
        # 返回最终的锯齿形层序遍历结果
        return result

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(m)，其中 m 是二叉树中某一层的最大节点数。队列最多存储一层的节点。

二叉树中的最大路径和

124. 二叉树中的最大路径和

路径定义

I 型路径：
- 是一条单线路径。
- 从某个节点出发，只能选择左子树或右子树向下延伸。
- 例如：1 -> 2 -> 3，路径不能分叉。
A 型路径：
- 是一条分叉路径。
- 从某个左子树出发，经过当前节点，再到右子树。
- 例如：2 -> 1 -> 3，路径会在当前节点分叉。
maxPathSum函数返回值是整个树中最大的A型路径和
dfs函数返回值是当前节点最大的I型路径和

解题要点

使用 DFS 遍历二叉树，从下往上计算每个节点的贡献值。
贡献值的定义：
- 从当前节点出发的 I 型路径 的最大和。
- 贡献值 = 当前节点值 + max(左子树贡献值, 右子树贡献值)
- 如果左子树或右子树的贡献值小于 0，则直接忽略
更新全局最大值：
- 通过 A 型路径 计算路径和：当前节点值 + 左子树贡献值 + 右子树贡献值。
- 更新全局最大值 res。
递归终止条件：
- 如果当前节点为空，返回贡献值 0。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def __init__(self):
        # 初始化全局最大值
        self.res = -float('inf')

    def dfs(self, root) -> int:
        # 如果当前节点为空，返回 0
        if not root:
            return 0
      
        # 递归计算左子树的贡献值，保证非负
        left = max(0, self.dfs(root.left))
        # 递归计算右子树的贡献值，保证非负
        right = max(0, self.dfs(root.right))
      
        # 更新全局最大值
        self.res = max(self.res, root.val + left + right)
      
        # 返回当前节点的贡献值
        return root.val + max(left, right)
  
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # 从根节点开始 DFS
        self.dfs(root)
        # 返回全局最大值
        return self.res

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点只被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。空间复杂度主要取决于递归调用栈的深度。

二叉树的右视图

199. 二叉树的右视图

解题要点

使用 deque 双端队列进行层序遍历。
在遍历每一层时，记录当前层的最后一个节点并将其值加入结果列表。
注意空树的情况，提前排除。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result
      
        # 初始化队列，加入根节点
        queue = deque([root])
      
        while len(queue) > 0:
            # 当前层的节点数量
            level_len = len(queue)
            # 遍历当前层的所有节点
            for i in range(level_len):
                node = queue.popleft()
                # 如果是当前层的最后一个节点，加入结果
                if i == level_len - 1:
                    result.append(node.val)
                # 将左子节点加入队列
                if node.left:
                    queue.append(node.left)
                # 将右子节点加入队列
                if node.right:
                    queue.append(node.right)
      
        return result

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(m)，其中 m 是二叉树中某一层的最大节点数。队列最多存储一层的节点。

二叉树的中序遍历

94. 二叉树的中序遍历

解题要点

中序遍历顺序：左子树 -> 根节点 -> 右子树。
递归方法：通过递归函数实现中序遍历，先递归左子树，然后访问根节点，最后递归右子树。
访问节点：在访问节点时，将节点值添加到结果列表中。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


from typing import List, Optional

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

class Solution:
    def __init__(self):
        self.res = []  # 初始化结果列表
  
    def dfs(self, root: Optional[TreeNode]) -> None:
        if not root:
            return 
        self.dfs(root.left)  # 递归遍历左子树
        self.res.append(root.val)  # 访问根节点
        self.dfs(root.right)  # 递归遍历右子树

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        self.dfs(root)  # 启动递归遍历
        return self.res  # 返回结果列表

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归栈的深度取决于二叉树的高度，最坏情况下为 O(n)(当树为链状时)，平均情况下为 O(log n)。

从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树

解题要点

通过preorder确定根节点，通过inorder划分左右子树
递归构建左子树和右子树
注意边界条件，当列表为空时返回None

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) :
        # 如果前序遍历列表为空，返回空节点
        if len(preorder) == 0:
            return None
        
        # 前序遍历的第一个元素是根节点的值
        root = preorder[0]
        
        # 在中序遍历列表中找到根节点的位置，用于划分左右子树
        index = inorder.index(root)
        
        # 递归构建左子树：
        # 前序遍历中左子树的部分是从第1个元素到index+1（不包括index+1）
        # 中序遍历中左子树的部分是从开始到index（不包括index）
        left = self.buildTree(preorder[1:index+1], inorder[:index])
        
        # 递归构建右子树：
        # 前序遍历中右子树的部分是从index+1开始到末尾
        # 中序遍历中右子树的部分是从index+1开始到末尾
        right = self.buildTree(preorder[index+1:], inorder[index+1:])
        
        # 创建根节点，并连接左右子树
        return TreeNode(val=root, left=left, right=right)

时空复杂度

时间复杂度：O(n^2)，其中 n 是二叉树的节点数。在最坏情况下，每次查找inorder中的根节点位置需要O(n)的时间，递归调用n次。
空间复杂度：O(n)，递归栈的深度为n。

求根到所有叶子节点的数字之和

129. 求根到叶子节点数字之和

解题要点

使用深度优先搜索（DFS）遍历二叉树。
维护一个路径数字，每访问一个节点，将当前节点的值加到路径数字中。
当遇到叶子节点时，将当前的路径数字加到总和中。
通过回溯的方式，确保路径数字在每次递归调用后能够正确回退。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def __init__(self):
        self.sum = 0
  
    def dfs(self, root, path):
        if not root:
            return 

        # 更新当前路径数字
        path = path * 10 + root.val

        # 如果当前节点是叶子节点，将路径数字加到总和中
        if not root.left and not root.right:
            self.sum += path 
      
        # 递归遍历左子树
        self.dfs(root.left, path)
        # 递归遍历右子树
        self.dfs(root.right, path)

        # 回溯，回退路径数字
        path = path // 10

    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        self.dfs(root, 0)
        return self.sum

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归调用栈的深度最多为树的高度。

对称二叉树

101. 对称二叉树

解题要点

判断二叉树是否对称，可以通过递归的方法，比较左子树和右子树是否镜像对称。
编写一个辅助函数isMirror，用于判断两棵树是否为镜像对称。
在isMirror函数中，递归地比较两棵树的左子树和右子树是否对称。
需要考虑空树的情况，提前判断。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def isMirror(self, left, right):
        # 如果两个节点都为空，则对称
        if not left and not right:
            return True
        # 如果其中一个节点为空，另一个不为空，则不对称
        if not left or not right:
            return False
        # 如果两个节点的值不相等，则不对称
        if left.val != right.val:
            return False 
        # 递归比较左子树的右子树和右子树的左子树，
        # 以及左子树的左子树和右子树的右子树
        return self.isMirror(left.right, right.left) \
           and self.isMirror(left.left, right.right)
  
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # 如果二叉树为空，直接返回True
        if not root:
            return True
        # 调用isMirror函数，判断左右子树是否镜像对称
        return self.isMirror(root.left, root.right)

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归调用栈的深度最大为树的高度。

二叉树的前序遍历

144. 二叉树的前序遍历

解题要点

前序遍历顺序：根节点 -> 左子树 -> 右子树。
使用递归方法实现前序遍历，注意递归终止条件。
可以用一个类属性 res 来存储遍历结果，简化代码。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution:
    def __init__(self):
        # 初始化一个空列表，用于存储遍历结果
        self.res = []
  
    def dfs(self, root):
        # 递归终止条件：如果当前节点为空，直接返回
        if not root:
            return 
      
        # 将当前节点的值加入结果列表
        self.res.append(root.val)
      
        # 递归遍历左子树
        self.dfs(root.left)
      
        # 递归遍历右子树
        self.dfs(root.right)

    def preorderTraversal(self, root):
        # 调用递归函数进行前序遍历
        self.dfs(root)
      
        # 返回遍历结果
        return self.res

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(n)，最坏情况下，递归栈的深度等于二叉树的高度，最坏情况下为 O(n)。

二叉树的最大深度

104. 二叉树的最大深度

解题要点

二叉树的最大深度：从根节点到最远叶子节点的最长路径上的节点数。
使用递归方法，二叉树的最大深度等于其左子树和右子树的最大深度加 1。
递归终止条件是当前节点为空，返回深度为 0。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def maxDepth(self, root):
        # 递归终止条件：如果当前节点为空，返回深度为 0
        if not root:
            return 0
      
        # 递归计算左子树的最大深度
        left_depth = self.maxDepth(root.left)
      
        # 递归计算右子树的最大深度
        right_depth = self.maxDepth(root.right)
      
        # 二叉树的最大深度等于左右子树的最大深度加 1
        return max(left_depth, right_depth) + 1

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归栈的深度最多为二叉树的高度。

平衡二叉树的判断

110. 平衡二叉树

解题要点

多用返回值：在递归过程中，如果发现某个节点的左右子树高度差的绝对值超过1，或者左子树或右子树本身不平衡，则返回-1表示不平衡。否则，返回当前节点的高度。
最终判断：如果递归调用的结果不是-1，则说明二叉树是平衡的。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def depth(self, root):
        # 递归计算二叉树的深度
        if not root:
            return 0
        left = self.depth(root.left)
        right = self.depth(root.right)
        # 如果左子树或右子树不平衡，则整个树不平衡
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        # 返回当前节点的深度
        return max(left, right) + 1

    def isBalanced(self, root):
        # 判断二叉树是否平衡
        return self.depth(root) != -1

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(n)，递归栈的深度取决于树的高度，最坏情况下树为单链表，高度为n。

关键点

递归函数的设计：depth函数不仅计算了当前节点的深度，还在计算过程中判断了子树是否平衡。
不平衡的判断：如果左子树或右子树的高度差超过1，或者左子树或右子树本身不平衡，则返回-1。
最终的判断：通过检查递归调用的结果是否为-1，来判断整个二叉树是否平衡。

验证二叉搜索树

98. 验证二叉搜索树

解题要点

为了验证一棵二叉树是否是二叉搜索树，我们可以利用二叉搜索树的一个关键性质：中序遍历结果是一个严格递增的序列。因此，我们可以对二叉树进行中序遍历，并在遍历过程中检查当前节点的值是否始终大于前一个节点的值。

具体步骤

初始化：定义一个全局变量 prev 来记录当前节点的前一个节点的值，初始化为负无穷大（-float('inf')）。定义另一个全局变量 valid 来记录当前是否还满足二叉搜索树的条件，初始化为 True。
中序遍历：对二叉树进行中序遍历。遍历顺序为：左子树 → 根节点 → 右子树。
- 递归遍历左子树。
- 检查当前节点的值是否严格大于 prev 的值（即前一个节点的值）。如果不满足，则将 valid 设置为 False。
- 更新 prev 为当前节点的值。
- 递归遍历右子树。
返回结果：遍历结束后，返回 valid 的值，即为该二叉树是否为二叉搜索树。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def __init__(self):
        self.prev = -float('inf')
        self.valid = True

    def dfs(self, root):
        if not root:
            return 
        self.dfs(root.left)
        self.valid = self.valid and root.val > self.prev
        self.prev = root.val 
        self.dfs(root.right)

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        self.dfs(root)
        return self.valid

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。我们需要访问每个节点一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归栈的深度取决于树的高度。在最坏情况下（树为链表形式），空间复杂度为 O(n)。

二叉树的直径

543. 二叉树的直径

解题要点

深度：一个节点深度，是这个节点到叶子节点的距离的最大值
直径：一个节点的直径，是左边深度加上右边深度
深度更新：这个节点的深度，是左右节点深度的最大值加一

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def __init__(self):
        self.res = 0  # 用于存储最大直径
  
    def dfs(self, root):
        if not root:
            return 0
        left = self.dfs(root.left)  # 递归计算左子树的深度
        right = self.dfs(root.right)  # 递归计算右子树的深度
        self.res = max(self.res, left + right)  # 更新最大直径
        return max(left, right) + 1  # 返回当前节点的深度

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.dfs(root)
        return self.res

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归调用栈的深度等于二叉树的高度。

路径总和 II

113. 路径总和 II

解题要点

记录时刻：不要在空节点才记录，要在叶子结点记录，前者会让同一个路径被记录两遍（一次遍历到叶子的左空节点，一次遍历到叶子的右空节点）

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution:
    def __init__(self):
        self.res = []
        self.target = 0

    def dfs(self, root, path):
        # 终止条件
        if not root:
            return 
        # 将当前节点的值加入路径
        path.append(root.val)
        # 如果是叶子节点且路径和等于目标值，将路径加入结果
        if not root.left and not root.right and sum(path) == self.target:
            self.res.append(path[:])
        # 递归遍历左子树和右子树
        self.dfs(root.left, path)
        self.dfs(root.right, path)
        # 回溯，将当前节点从路径中移除
        path.pop()

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        self.target = targetSum
        self.dfs(root, [])
        return self.res

时空复杂度

时间复杂度：O(n^2)，其中 n 是二叉树的节点数。最坏情况下，二叉树退化为链表，需要遍历所有路径，且每条路径的求和操作需要 O(n) 时间。
空间复杂度：O(n)，递归栈的深度最多为 n，路径列表的空间也是 O(n)。

二叉树的最大宽度

662. 二叉树的最大宽度

解题要点

层序遍历时，记录每个节点的位置信息。利用完全二叉树的性质，父节点的位置为pos，则左子节点的位置为2*pos，右子节点的位置为2*pos + 1。
每层遍历结束后，计算当前层的宽度（即该层最右侧节点位置减去最左侧节点位置加1），并更新最大宽度。
使用两个队列分别存储节点和节点的位置信息。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


from collections import deque

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # 如果二叉树为空，宽度为0
        res = 0
        if not root:
            return res
      
        # 初始化队列，存储节点和节点的位置信息
        q_node = deque([root])
        q_pos = deque([0])
      
        # 当队列不为空时，继续遍历
        while len(q_node):
            level = []  # 存储当前层节点的位置信息
            level_len = len(q_node)  # 当前层的节点数量
          
            # 遍历当前层的所有节点
            for _ in range(level_len):
                node = q_node.popleft()  # 从队列中取出节点
                pos = q_pos.popleft()  # 从队列中取出节点位置
                level.append(pos)  # 将节点位置加入当前层
              
                # 如果当前节点有左子节点，将其加入队列
                if node.left:
                    q_node.append(node.left)
                    q_pos.append(2 * pos)
              
                # 如果当前节点有右子节点，将其加入队列
                if node.right:
                    q_node.append(node.right)
                    q_pos.append(2 * pos + 1)
          
            # 计算当前层的宽度，并更新最大宽度
            res = max(res, level[-1] - level[0] + 1)
      
        # 返回二叉树的最大宽度
        return res

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(m)，其中 m 是二叉树中某一层的最大节点数。队列最多存储一层的节点。

路径总和

112. 路径总和

解题思路

深度优先搜索（DFS）：从根节点开始遍历每一条路径，累加路径上的节点值。
递归终止条件：当到达叶子节点时，判断当前路径的节点值之和是否等于目标和。
返回结果：如果存在这样的路径，返回 True，否则返回 False。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def __init__(self):
        self.res = False
        self.target = 0

    def dfs(self, root, path):
        if not root:
            return
        # 累加当前节点的值
        path += root.val
        # 如果当前节点是叶子节点，判断路径和是否等于目标值
        if not root.left and not root.right:
            self.res = self.res or path == self.target
        # 递归遍历左子树
        self.dfs(root.left, path)
        # 递归遍历右子树
        self.dfs(root.right, path)

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        self.target = targetSum
        self.dfs(root, 0)
        return self.res

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归调用栈的深度取决于树的高度。在最坏情况下，树是一个链表，空间复杂度为 O(n)。

翻转二叉树

226. 翻转二叉树

解题要点

使用递归的方法来翻转二叉树，递归的基本情况是当前节点为空，直接返回None。
对于当前节点，交换其左子节点和右子节点。
递归地对左子节点和右子节点进行同样的翻转操作。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 如果根节点为空，直接返回空
        if not root:
            return None 
      
        # 交换当前节点的左右子节点
        root.left, root.right = root.right, root.left
      
        # 递归地翻转左子树
        self.invertTree(root.left)
        # 递归地翻转右子树
        self.invertTree(root.right)
      
        # 返回翻转后的根节点
        return root

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归栈的深度最多为 h。在平均情况下，二叉树的层数为O(log n)，在最坏情况下（二叉树退化为链表），层数为O(n)。

二叉树的序列化与反序列化

297. 二叉树的序列化与反序列化

问题描述

设计一个算法，实现二叉树的序列化与反序列化。序列化是将一个二叉树转换成一个字符串，而反序列化则是将这个字符串重建成原始的二叉树结构。你可以自定义序列化和反序列化的格式，但需要保证二叉树的结构能够被准确无误地重建。

解题要点

序列化：使用深度优先搜索（DFS）前序遍历二叉树，将节点的值转换为字符串，并用特定的分隔符（如逗号）分隔。空节点用特殊字符（如#）表示。
反序列化：根据序列化得到的字符串，使用递归的方法重建二叉树。每次读取一个节点的值，如果是特殊字符#，则返回None，否则创建一个新节点，并递归地构建其左子树和右子树。
使用全局变量或类成员变量：在反序列化过程中，需要跟踪当前处理的字符串索引，可以通过类成员变量或全局变量来实现。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


from collections import deque

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

class Codec:
    def serialize(self, root):
        def dfs(node):
            if not node:
                return "#"
            return str(node.val) + "," + dfs(node.left) + "," + dfs(node.right)
        return dfs(root)

    def deserialize(self, data):
        self.idx = 0
        vals = data.split(",")
      
        def dfs():
            if vals[self.idx] == "#":
                self.idx += 1
                return None
            node = TreeNode(val=vals[self.idx])
            self.idx += 1
            node.left = dfs()
            node.right = dfs()
            return node
        return dfs()

时空复杂度

序列化：
- 时间复杂度：O(n)，其中n是二叉树的节点数。每个节点被访问一次。
- 空间复杂度：O(n)，递归调用栈的深度在最坏情况下是O(n)。
反序列化：
- 时间复杂度：O(n)，其中n是二叉树的节点数。每个节点被访问一次。
- 空间复杂度：O(n)，递归调用栈的深度在最坏情况下是O(n)。

完全二叉树的判断

958. 完全二叉树的判断

解题要点

完全二叉树的定义：完全二叉树是指除了最后一层外，其余各层的节点数都达到最大值，且最后一层的节点都连续集中在最左边。
层序遍历：使用层序遍历（BFS）来检查二叉树是否满足完全二叉树的条件。
标记结束：通过一个标记end来记录是否已经开始遍历到空节点，如果在遍历过程中发现了非空节点且end为True，则说明二叉树不是完全二叉树。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


from collections import deque

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        # 如果二叉树为空，直接返回True
        if not root:
            return True
      
        # 初始化队列，将根节点加入队列
        queue = deque([root])
        # 标记是否已经开始遍历到空节点
        end = False

        # 当队列不为空时，继续遍历
        while queue:
            # 从队列中取出一个节点
            node = queue.popleft()

            # 如果已经遍历到空节点，且当前节点非空，返回False
            if end and node:
                return False 
          
            # 如果当前节点为空，标记end为True，继续下一次循环
            if not node:
                end = True 
                continue 
          
            # 将当前节点的左子节点加入队列
            queue.append(node.left)
            # 将当前节点的右子节点加入队列
            queue.append(node.right)

        # 遍历结束后，返回True，说明是完全二叉树
        return True

代码解释

初始化队列：将根节点加入队列。
遍历队列：每次从队列中取出一个节点，检查是否已经遍历到空节点。
- 如果已经遍历到空节点，并且当前节点非空，则返回False，说明二叉树不是完全二叉树。
- 如果当前节点为空，标记end为True，表示已经开始遍历到空节点，继续下一次循环。
- 将当前节点的左子节点和右子节点加入队列。
返回结果：如果遍历结束后没有发现不符合条件的节点，则返回True，说明二叉树是完全二叉树。

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(m)，其中 m 是二叉树中某一层的最大节点数。队列最多存储一层的节点。