二叉树中和为某一值的路径

soulballad约 1036 字大约 3 分钟

题目：

输入域一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。二叉树节点的定义如下：
public class BinaryTreeNode {

    public int value;
    public BinaryTreeNode left;
    public BinaryTreeNode right;
}
例如，输入下图所示二叉树的整数 22，则打印出两条路径，第一条路径包含节点 10、12，第二条路径包含节点 10、5、7。

分析：

由于是从根节点开始到叶节点形成一条路径，也就是说总是以根节点为起始点，因此首先要遍历根节点。在树的前序、中序、后序 3 种遍历方式中，只有前序遍历是先访问根节点。
按照前序遍历上图二叉树，访问节点 10 之后，会访问节点 5。从二叉树的定义可以看出，子节点无法获取父节点，在访问节点 5 的时候，无法知道前面经过了哪些节点，所以需要把经过的节点保存下来。没访问一个节点，就把当前节点添加到路径中去。当访问节点 5时，路径包含两个节点，值分别是 10 和 5。接下来遍历节点4，把它也加入路径中，这时已经到达叶节点，但路径上3个数之和是19，不等于 22，因此不是符合要求的路径。
接着遍历其他节点。在遍历下一个节点之前，要先从节点 4 回到节点 5，再去遍历节点 5的右子节点7。在回到节点 5 的时候，由于节点 4已经不在访问节点 7 的路径上了，所以需要把节点 4 从路径中删除。访问节点 7 的时候，再把该节点加入路径。此时路径中3个节点为：10、5、7，和刚好是22，符合要求。
同理遍历根节点的右子树。

下表显示整个遍历过程

步骤	操作	是否叶节点	路径	路径节点之和
1	访问节点10	否	10	10
2	访问节点5	否	10、5	15
3	访问节点4	是	10、5、4	19
4	回到节点5		10、5	15
5	访问节点7	是	10、5、7	22
6	回到节点5		10、5	15
7	回到节点10		10	10
8	访问节点12	是	10、12	22

代码：

public class FindPathInBinaryTree {

    /**
     * 查找路径
     *
     * @param pRoot       二叉树根节点
     * @param expectedSum 输入值
     */
    public static void findPath(BinaryTreeNode pRoot, int expectedSum) {
        if (null == pRoot) {
            return;
        }

        Stack<Integer> path = new Stack<>();
        int currentSum = 0;
        findPath(pRoot, expectedSum, path, currentSum);
    }

    /**
     * 查找路径
     *
     * @param pRoot       二叉树根节点
     * @param expectedSum 输入值
     * @param path        路径
     * @param currentSum  当前路径之和
     */
    private static void findPath(BinaryTreeNode pRoot, int expectedSum, Stack<Integer> path, int currentSum) {
        currentSum += pRoot.value;
        // 把当前节点值放入路径
        path.push(pRoot.value);

        // 判断是否是叶节点
        boolean isLeaf = pRoot.left == null && pRoot.right == null;
        // 如果是叶节点，并且路径之和等于输入值，打印这条路径
        if (isLeaf && currentSum == expectedSum) {
            System.out.println("a path is found: " + path.toString());
        }

        // 如果不是叶节点，则遍历它的子节点
        if (pRoot.left != null) {
            findPath(pRoot.left, expectedSum, path, currentSum);
        }
        if (pRoot.right != null) {
            findPath(pRoot.right, expectedSum, path, currentSum);
        }

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

牛客精简解法：

public class NewCodeSolution {

    private static List<List<Integer>> listAll = new ArrayList<>();
    private static List<Integer> list = new ArrayList<>();

    public static List<List<Integer>> findPath(BinaryTreeNode pRoot, int target) {

        if (pRoot == null) {
            return listAll;
        }

        list.add(pRoot.value);
        target -= pRoot.value;

        if (target == 0 && pRoot.left == null && pRoot.right == null) {
            // 这里注意要新建一个list，因为后面有remove
            listAll.add(new ArrayList<>(list));
        }

        findPath(pRoot.left, target);
        findPath(pRoot.right, target);

        list.remove(list.size() - 1);
        return listAll;
    }
}

测试：

public class TestFindPathInTree {

    BinaryTreeNode root1 = new BinaryTreeNode(10);

    @Before
    public void before() {

        BinaryTreeNode nodeA21 = new BinaryTreeNode(5);
        BinaryTreeNode nodeA22 = new BinaryTreeNode(12);
        BinaryTreeNode nodeA31 = new BinaryTreeNode(4);
        BinaryTreeNode nodeA32 = new BinaryTreeNode(7);

        buildTree(root1, nodeA21, nodeA22);
        buildTree(nodeA21, nodeA31, nodeA32);
    }

    private void buildTree(BinaryTreeNode root, BinaryTreeNode left, BinaryTreeNode right) {
        root.left = left;
        root.right =right;
    }

    @Test
    public void test() {
        FindPathInBinaryTree.findPath(root1, 22);
    }
    
        @Test
    public void test2() {
        List<List<Integer>> path = NewCodeSolution.findPath(root1, 22);
        System.out.println(JSON.toJSONString(path));
    }
}