《剑指offer第二版》面试题34：二叉树中和为某一值得路径（j

题目描述

输入一颗二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶子节点所经过的节点形成一条路径。

解题思路:

1. 定义一个辅助栈，用于保存当前经过的节点。定义一个辅助变量num，用于保存辅助栈中路径的和。
2. 前序遍历子树，遍历节点的时候，先将该节点压入辅助栈，并更新num。
   1. 如果如果当前是叶子节点，并且num等于输入的值，则说明找到了一条路径，打印stack里的路径。
   2. 如果不是叶子节点，则继续遍历左右子树。
   3. 遍历完左右子树后，返回父节点前，在路径上删除当前节点。

代码

void printPathWithNum(TreeNode root, int targetNum){
    if (root == null) {
        return;
    }

    Stack<TreeNode> pathHolder = new Stack<>();
    printPathWithNum(root, pathHolder, 0, targetNum);
}

void printPathWithNum(TreeNode root, Stack<TreeNode> pathHolder, int num, int targetNum){
    if (root == null) {
        return;
    }
    num = num + root.value;
    pathHolder.push(root);
    if (root.left == null && root.right == null) {
        // 如果是叶子节点，并且路径上节点值等于输入的值，则打印出这条路径
        if (num == targetNum) {
            System.out.println();
            for (int i = 0; i < pathHolder.size(); i++) {
                System.out.print(pathHolder.get(i).value + " ");
            }
            pathHolder.pop();
            return;
        }
    }

    // 如果不是叶子节点，则遍历其左右子树
    if (root.left != null) {
        printPathWithNum(root.left, pathHolder, num, targetNum);
    }
    if (root.right != null) {
        printPathWithNum(root.right, pathHolder, num, targetNum);
    }

    // 返回父节点前，在路径上删除当前节点
    pathHolder.pop();
}