二叉搜索树：从最底层到根节点的优雅遍历实现方法

嘿，你要的这种遍历其实就是自底向上的层序遍历——从最底层节点开始，每层内保持左到右的顺序，一直遍历到根节点。刚好我可以给你递归和迭代两种实现方案，用Python来举例，思路在其他语言里也通用：

思路 #

递归的核心是记录每个节点所在的层级（把根节点算作第0层，子节点层级依次+1），用一个字典来存储每一层对应的节点值列表。递归遍历完成后，我们只需要从最高层级（也就是最底层）到第0层（根节点），把所有层级的节点值依次拼接起来，就能得到想要的结果。

代码示例 #

首先定义二叉树节点的基础类：

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

然后是递归实现的遍历函数：

def bottom_up_traversal_recursive(root):
    # 用字典存储每个层级对应的节点值列表
    level_nodes = {}
    
    def traverse(node, current_level):
        if not node:
            return
        # 如果当前层级还没在字典里，初始化空列表
        if current_level not in level_nodes:
            level_nodes[current_level] = []
        # 将当前节点值加入对应层级的列表
        level_nodes[current_level].append(node.val)
        # 递归遍历左、右子树，层级+1
        traverse(node.left, current_level + 1)
        traverse(node.right, current_level + 1)
    
    # 从根节点（层级0）开始遍历
    traverse(root, 0)
    # 反转层级顺序，拼接所有节点值
    return [val for level in reversed(level_nodes.keys()) for val in level_nodes[level]]

思路 #

迭代的方式可以借助队列实现普通的从上到下层序遍历，把每一层的节点值单独存为一个子列表。遍历完成后，将这些子列表的顺序反转，再展开成一个一维列表，就得到了自底向上的遍历结果。这种方式不需要递归调用栈，适合处理较大的树结构，避免栈溢出问题。

代码示例 #

from collections import deque

def bottom_up_traversal_iterative(root):
    if not root:
        return []
    
    # 存储每一层的节点值列表
    level_results = []
    # 队列用于层序遍历初始化，先放入根节点
    queue = deque([root])
    
    while queue:
        # 获取当前层的节点数量
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            # 左子节点存在则加入队列
            if node.left:
                queue.append(node.left)
            # 右子节点存在则加入队列
            if node.right:
                queue.append(node.right)
        
        # 将当前层的结果加入列表
        level_results.append(current_level)
    
    # 反转层级顺序，再展开为一维列表
    return [val for level in reversed(level_results) for val in level]

按照你给出的示例树结构（根节点A，左子节点B，右子节点C；B的左子节点D、右子节点E；C的右子节点G），我们可以构造树并测试两种实现：

# 构造示例树节点
d_node = TreeNode('D')
e_node = TreeNode('E')
g_node = TreeNode('G')
b_node = TreeNode('B', d_node, e_node)
c_node = TreeNode('C', None, g_node)
a_node = TreeNode('A', b_node, c_node)

# 测试递归实现
print(bottom_up_traversal_recursive(a_node))  # 输出: ['D', 'E', 'G', 'B', 'C', 'A']

# 测试迭代实现
print(bottom_up_traversal_iterative(a_node))  # 输出: ['D', 'E', 'G', 'B', 'C', 'A']

内容的提问来源于stack exchange，提问作者kklaw