面试：遍历一个树结构有哪些方法？

在Java中遍历树结构，主要有两种核心策略：深度优先遍历和广度优先遍历。

深度优先遍历

一路向下，深入到底。先沿着分支尽可能深地访问节点，直至末端再回溯。常见的实现方式有递归、栈。

递归实现

递归是实现DFS最直观的方式。代码非常简洁，其逻辑是：如果当前节点为空，则返回；否则，先访问当前节点，然后递归地遍历其每个子节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// 以多叉树为例
class TreeNode {
    int value;
    List<TreeNode> children;
    // ... 构造方法等
}

public void dfsRecursive(TreeNode node) {
    if (node == null) return;
    // 1. 访问当前节点 (位于此处在二叉树中即为“前序遍历”)
    System.out.print(node.value + " ");
    // 2. 递归遍历每个子节点
    for (TreeNode child : node.children) {
        dfsRecursive(child);
    }
}

栈实现

通过显式地使用栈来模拟递归过程，可以避免递归深度过大可能引发的栈溢出错误。其核心步骤是先将根节点压入栈，然后在循环中弹出栈顶节点并访问，接着逆序将该节点的子节点压入栈中

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public void dfsWithStack(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode currentNode = stack.pop();
        // 访问节点
        System.out.print(currentNode.value + " ");
        // 将子节点逆序压入栈，保证正序弹出
        for (int i = currentNode.children.size() - 1; i >= 0; i--) {
            stack.push(currentNode.children.get(i));
        }
    }
}

广度优先遍历

广度优先遍历使用队列实现，非常适合需要按层级分析树结构的场景。

队列实现

核心步骤是先将根节点加入队列，然后在循环中从队列头部取出节点并访问，再将该节点的所有子节点依次加入队列尾部

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public void breadthFirstTraversal(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root); // 根节点入队

    while (!queue.isEmpty()) {
        TreeNode currentNode = queue.poll(); // 取出队首节点
        // 访问节点
        System.out.print(currentNode.value + " ");
        // 将当前节点的所有子节点入队
        for (TreeNode child : currentNode.children) {
            queue.offer(child);
        }
    }
}