计算机基础

引言 (Introduction)

在算法的进阶阶段，我们不再满足于自顶向下的简单递归。如何处理跨越根节点的全局最优路径？如何脱离递归栈，利用树本身的空闲指针实现 $O(1)$ 空间复杂度的遍历？如何将内存中的树结构无损地持久化到磁盘？

本文是本系列终篇，将深入剖析这些高难度、高频考点的二叉树算法。所有代码基于标准节点定义：

from typing import Optional, List

class TreeNode:
    def __init__(self, val: int = 0, left: 'Optional[TreeNode]' = None, right: 'Optional[TreeNode]' = None):
        self.val = val
        self.left = left
        self.right = right

1. 复杂路径：二叉树中的最大路径和

题目描述：路径被定义为一条从树中任意节点出发，达到任意节点的序列。求该路径节点值之和的最大值（LeetCode 124）。

核心难点：路径可能不经过根节点，也可能是一个倒 “V” 型结构（即左子树 -> 根 -> 右子树）。 破解思路： 我们需要在递归函数中区分两个概念：

  1. 全局最大值 max_sum：记录遍历过程中遇到的最大倒 “V” 型路径和（即允许同时包含左右子树）。
  2. 函数的返回值：返回给父节点的最大单边贡献值（只能选左边或右边，因为路径不能分叉超过一次）。
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = -float('inf')
        
        def max_gain(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
                
            # 递归计算左右子树的最大贡献值
            # 只有当贡献值为正数时才采纳（如果为负，不如不选，记为 0）
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)
            
            # 计算以当前节点为顶点的倒 "V" 型路径和，并尝试更新全局最大值
            current_path_sum = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, current_path_sum)
            
            # 返回当前节点对其父节点的最大单边贡献
            return node.val + max(left_gain, right_gain)
            
        max_gain(root)
        return int(self.max_sum)

2. 空间极致优化：Morris 遍历

常规的 DFS 无论迭代还是递归，都需要 $O(H)$ 的空间复杂度来保存回溯路径。Morris 遍历（线索二叉树 Threaded Binary Tree 思想的延伸）通过临时修改叶子节点的空闲 right 指针，将其指向中序遍历的后继节点，从而实现了惊人的 $O(1)$ 额外空间复杂度。

2.1 Morris 中序遍历逻辑拆解

  1. 如果当前节点 curr 没有左子树，说明当前是最小节点，访问它，并向右走。
  2. 如果有左子树，找到左子树中的最右侧节点（即中序遍历下 curr 的前驱节点 pre）：
    • 如果 pre.right 为空，说明还没线索化，将其指向 curr，然后 curr 向左走。
    • 如果 pre.right 指向 curr，说明左边已遍历完，这是线索找回来的，断开线索恢复原状，访问 curr，并向右走。
def morris_inorder(root: Optional[TreeNode]) -> List[int]:
    """Morris 中序遍历，空间复杂度 O(1)"""
    res: List[int] = []
    curr = root
    
    while curr:
        if not curr.left:
            # 1. 没有左子树，直接访问当前节点，然后走向右边（可能是真实的右孩子，也可能是线索）
            res.append(curr.val)
            curr = curr.right
        else:
            # 2. 有左子树，寻找前驱节点（左子树的最右节点）
            pre = curr.left
            while pre.right and pre.right != curr:
                pre = pre.right
            
            if not pre.right:
                # 建立线索，指向当前节点，然后继续往左深入
                pre.right = curr
                curr = curr.left
            else:
                # 线索已经存在，说明左子树已经遍历完毕。断开线索恢复树结构。
                pre.right = None
                res.append(curr.val)
                curr = curr.right
                
    return res

3. 持久化技术：序列化与反序列化

序列化是将数据结构转化为字符串的过程，反序列化则是其逆过程。使用层序遍历（BFS）是一种非常直观且易于调试的序列化方式。为了在反序列化时准确定位空节点，我们必须显式地将 None 存储为 "null"。

from collections import deque

class Codec:
    """二叉树的序列化与反序列化"""
    def serialize(self, root: Optional[TreeNode]) -> str:
        """编码树结构"""
        if not root:
            return "[]"
            
        queue = deque([root])
        res: List[str] = []
        
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append("null")
                
        # 去除末尾多余的 null
        while res and res[-1] == "null":
            res.pop()
            
        return "[" + ",".join(res) + "]"

    def deserialize(self, data: str) -> Optional[TreeNode]:
        """解码字符串恢复树结构"""
        if data == "[]":
            return None
            
        vals = data[1:-1].split(",")
        root = TreeNode(int(vals[0]))
        queue = deque([root])
        i = 1
        
        while queue and i < len(vals):
            node = queue.popleft()
            
            # 重建左孩子
            if vals[i] != "null":
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            
            # 重建右孩子 (注意越界检查)
            if i < len(vals) and vals[i] != "null":
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
            
        return root

结论 (Conclusion)

从最大路径和的全局与局部状态剥离，到 Morris 遍历对树底端冗余指针的极致利用，再到工程实践中必不可少的序列化手段——掌握这些高阶算法，不仅能让你在面试中脱颖而出，更能深刻重塑你对数据结构内存模型的理解。至此，二叉树的旅程告一段落，但树的智慧远未结束。