二叉树深度优先遍历变种面试题精讲与答案

在一次研究院的技术面试中，遇到一道精巧的二叉树算法题，现将解题思路与实现分享给大家。

题目描述如下：

有一棵二叉树，每个节点存有一个整数值。需要从每一个叶子节点开始，沿父指针向上回溯至根节点，找出所有节点值之和等于给定目标值的完整路径。

例如下图，当目标总和为 14 时，应输出以下两条路径：

3 → 6 → 5
3 → 7 → 4

该题目本质上是二叉树深度优先遍历（DFS）的变体，核心在于利用栈机制实现精确的回溯控制。实现代码如下：

package cn.outofmemory;

import ja va.util.Stack;

public class TreeSum {
    public static void main(String[] args) {
        int expectSum = 22;

        // declare tree
        TreeNode root = new TreeNode(12,
                new TreeNode(6, new TreeNode(4), new TreeNode(7)),
                new TreeNode(3, new TreeNode(2), new TreeNode(7)));

        Stack stack = new Stack();
        stack.add(new StackData(root, NodeType.root));

        while (!stack.isEmpty()) {
            StackData top = stack.peek();
            TreeNode temp = top.value;

            // 如果栈顶元素是叶子节点，计算路径和是否满足条件
            if (temp.isLeaf()) {
                int sumOfStack = getSumOfStack(stack);
                if (sumOfStack == expectSum) {
                    printStack(stack);
                }
                // 弹出叶子节点
                stack.pop();
                if (top.nodeType == NodeType.left) {
                    temp = stack.peek().value;
                    // 如果有右子树，将右子树放入栈顶；否则循环弹出直到遇到有右子树的节点
                    if (temp.getRightNode() == null) {
                        while (temp.getRightNode() == null) {
                            StackData popAgain = stack.peek();
                            if (popAgain.value.getRightNode() == null) {
                                popAgain = stack.pop();
                                temp = popAgain.value;
                            }
                        }
                    } else {
                        stack.push(new StackData(temp.getRightNode(), NodeType.right));
                    }
                    continue;
                } else if (top.nodeType == NodeType.right) {
                    // 叶子节点是右子节点，再次弹出
                    StackData popAgain = stack.pop();
                    while (popAgain.nodeType == NodeType.right) {
                        popAgain = stack.pop();
                    }
                    if (!stack.isEmpty()) {
                        StackData nowTop = stack.peek();
                        if (nowTop.value.getRightNode() != null) {
                            stack.push(new StackData(nowTop.value.getRightNode(), NodeType.right));
                        }
                    }
                } else {
                    // 根节点说明遍历结束，弹出并结束循环
                    stack.pop();
                    continue;
                }
            } else {
                // 将所有左子节点压栈
                while (temp.getLeftNode() != null) {
                    temp = temp.getLeftNode();
                    stack.add(new StackData(temp, NodeType.left));
                }
            }
        }
    }

    private static void printStack(Stack stack) {
        for (StackData sd : stack) {
            System.out.print("" + sd.value.getValue() + " ");
        }
        System.out.println();
    }

    private static int getSumOfStack(Stack stack) {
        int result = 0;
        for (StackData sd : stack) {
            result += sd.value.getValue();
        }
        return result;
    }
}

配套的 TreeNode 类定义如下：

package cn.outofmemory;

public class TreeNode {
    public TreeNode() {}
    public TreeNode(int value) { this.value = value; }
    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.setLeftNode(left);
        this.setRightNode(right);
    }

    private TreeNode left;
    private TreeNode right;
    private int value;

    protected void setLeftNode(TreeNode left) { this.left = left; }
    public TreeNode getLeftNode() { return this.left; }
    protected void setRightNode(TreeNode right) { this.right = right; }
    public TreeNode getRightNode() { return this.right; }
    public int getValue() { return this.value; }
    public boolean isLeaf() { return this.left == null && this.right == null; }
}

枚举类型 NodeType 的定义：

package cn.outofmemory;

public enum NodeType {
    root, left, right
}

辅助类 StackData 用于封装节点及其类型，便于栈操作中区分左右子树：

package cn.outofmemory;

public class StackData {
    public TreeNode value;
    public NodeType nodeType;

    public StackData(TreeNode value, NodeType type) {
        this.value = value;
        this.nodeType = type;
    }
}

该题核心是对深度优先遍历的增强：不仅完成节点遍历，还需在回溯时记录节点类型（左子、右子或根节点），从而正确恢复遍历路径。借助自定义栈的数据结构，可以精准控制入栈与出栈时机，并动态计算路径和。掌握这一思路后，类似变种题目均可举一反三。