Python面试宝典第8题：二叉树遍历

题目

        给定一棵二叉树的根节点 root ，返回它节点值的前序遍历。

        示例 1：

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

        示例 2：

输入：root = []
输出：[]

        示例 3：

输入：root = [1]
输出：[1]

基础知识

        二叉树属于一种常用的数据结构，是一个由零个或多个节点组成的层次结构。二叉树具有以下特征：

        1、每个节点最多有两个子节点，分别称为左子节点和右子节点。

        2、根节点位于树的最顶端，没有父节点。

        3、叶子节点没有子节点。

        4、非叶子节点至少有一个子节点。

        前序遍历是二叉树遍历的一种方式，其顺序遵循“根节点 -> 左子树 -> 右子树”的原则。具体步骤如下：

        1、访问当前节点：首先处理当前节点（打印节点值，或进行其他操作）。

        2、递归地遍历左子树：然后对当前节点的左子树进行前序遍历。

        3、递归地遍历右子树：最后对当前节点的右子树进行前序遍历。

        假如我们有以下的二叉树，则其前序遍历的顺序为：1 -> 2 -> 4 -> 5 -> 3。

    1
   / \
  2   3
 / \
4   5

递归法

        对于给定的二叉树，我们可以通过递归的方式来实现前序遍历。下面我们给出了用递归法解题的示例代码，具体的解题步骤如下。

        1、binary_tree_traversal_recursive 函数接收一个 TreeNode 类型的参数 root，它代表二叉树的根节点。函数内部定义了另一个名为 dfs 的辅助函数，该函数负责实际的递归遍历工作。

        2、在 dfs 函数中，我们先访问当前节点，然后递归访问左子树，最后递归访问右子树。

        3、遍历完成后，所有节点都已访问，dfs 函数逐级返回，最终 binary_tree_traversal_recursive 函数返回结果列表 result。

from typing import List

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

def binary_tree_traversal_recursive(root: TreeNode) -> List[int]:
    result = []

    def dfs(node):
        if node is None:
            return
        
        # 访问当前节点
        result.append(node.val)
        # 递归访问左子树
        dfs(node.left)
        # 递归访问右子树
        dfs(node.right)

    dfs(root)
    return result

right = TreeNode(2)
root = TreeNode(1, None, right)
right.left = TreeNode(3)
result = binary_tree_traversal_recursive(root)
print(result)

迭代法

        迭代法实现二叉树的前序遍历，关键在于利用栈来模拟递归的过程，确保节点的访问顺序符合“根节点 -> 左子树 -> 右子树”的规则。使用迭代法求解本题的主要步骤如下。

        1、初始化。创建一个栈，并将根节点压入栈中。同时，创建一个结果列表用于存放遍历结果。

        2、循环处理。当栈不为空时，执行以下操作：

        （1）弹出栈顶元素。将栈顶元素弹出，并将其值添加到结果列表中，这是因为前序遍历先访问根节点。

        （2）处理右子树。如果当前节点有右子节点，将右子节点压入栈中。这是因为，右子节点应当在其左子树访问完后再访问，故右子节点应最后处理。

        （3）处理左子树。如果当前节点有左子节点，将左子节点压入栈中。这是因为，左子节点应在当前节点的右子节点之前访问。

        3、结束条件。当栈为空时，所有节点都被访问过，遍历结束。

        根据上面的算法步骤，我们可以得出下面的示例代码。

from typing import List

def binary_tree_traversal_iteration(root: TreeNode) -> List[int]:
    if not root:
        return []
    
    stack, result = [root, ], []
    while stack:
        # 弹出栈顶元素并访问
        node = stack.pop()
        if node:
            # 访问栈顶节点
            result.append(node.val)
            
            # 栈顶元素出栈后，先压右子节点，保证右子节点最后访问
            if node.right:
                stack.append(node.right)

            # 然后压左子节点
            if node.left:
                stack.append(node.left)
    
    return result

right = TreeNode(2)
root = TreeNode(1, None, right)
right.left = TreeNode(3)
result = binary_tree_traversal_iteration(root)
print(result)

总结

        递归法的时间复杂度为O(n)，每个节点被访问一次。空间复杂度最好情况下为O(log n)（此时为平衡树），最坏情况下为O(n)（此时为高度为n的斜树）。递归法的实现直观反映了前序遍历的逻辑，即“根-左-右”，但存在栈溢出、空间复杂度较高等缺点。

        迭代法的时间复杂度也为O(n)，每个节点被访问一次。空间复杂度为O(h)，其中h是树的高度。对于平衡树来说为O(log n)，最坏情况下（高度为n的斜树）为O(n)。相较于递归法，迭代法使用显式栈管理，空间复杂度更加可控。此外，迭代法没有递归调用栈的限制，适用于处理大规模或深度极大的二叉树。