【剑指Offer 25】二叉树中和为某一值的路径

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

代码如下：

package demo;

import java.util.ArrayList;
import java.util.List;

public class Test25 {
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }

    /**
     * @param root
     *            树的根节点
     * @param expectedSum
     *            要求的路径和
     */
    public static void findPath(BinaryTreeNode root, int expectedSum) {
        // 创建一个链表，用于存放根结点到当前处理结点所经过的结点
        List<Integer> list = new ArrayList<>();
        if (root != null) {
            // 调用辅助处理方法
            findPath(root, 0, expectedSum, list);
        }
    }

    /**
     * @param root
     *            当前要处理的结点
     * @param curSum
     *            当前记录的和
     * @param expectedSum
     *            要求的路径和
     * @param list
     *            根节点到当前处理结点所经过的结点
     */
    private static void findPath(BinaryTreeNode root, int curSum, int expectedSum, List<Integer> list) {
        if (root != null) {
            // 当前记录的和，加上当前结点的值
            curSum += root.value;
            // 将当前结点入队
            list.add(root.value);
            // 如果当前记录的和 < 要求的路径和
            if (curSum < expectedSum) {
                // 递归处理左子树
                findPath(root.left, curSum, expectedSum, list);
                // 递归处理右子树
                findPath(root.right, curSum, expectedSum, list);
            }
            // 如果当前记录的和 == 要求的路径和
            else if (curSum == expectedSum) {
                // 当前结点是叶子结点，则输出结果
                if (root.left == null && root.right == null) {
                    System.out.println(list);
                }
            }
            // 移除当前结点
            list.remove(list.size() - 1);
        }
    }
}

测试1：

测试1

public static void main(String[] args) {
    BinaryTreeNode root1 = new BinaryTreeNode();
    root1.value = 10;
    root1.left = new BinaryTreeNode();
    root1.left.value = 5;
    root1.right = new BinaryTreeNode();
    root1.right.value = 12;
    root1.left.left = new BinaryTreeNode();
    root1.left.left.value = 4;
    root1.left.right = new BinaryTreeNode();
    root1.left.right.value = 7;
    System.out.println("有2条路径上的结点和为22：");
    findPath(root1, 22);
    System.out.println("没有路径上的结点和为15：");
    findPath(root1, 15);
    System.out.println("有1条路径上 结点和为19：");
    findPath(root1, 19);
}

运行结果

测试2：

测试2

public static void main(String[] args) {
    BinaryTreeNode root2 = new BinaryTreeNode();
    root2.value = 5;
    root2.left = new BinaryTreeNode();
    root2.left.value = 4;
    root2.left.left = new BinaryTreeNode();
    root2.left.left.value = 3;
    root2.left.left.left = new BinaryTreeNode();
    root2.left.left.left.value = 2;
    root2.left.left.left.left = new BinaryTreeNode();
    root2.left.left.left.left.value = 1;
    System.out.println("有1条路径上的结点和为15：");
    findPath(root2, 15);
    System.out.println("没有路径上的结点和为16：");
    findPath(root2, 16);
}

运行结果

测试3：

测试3

public static void main(String[] args) {
    BinaryTreeNode root3 = new BinaryTreeNode();
    root3.value = 1;
    root3.right = new BinaryTreeNode();
    root3.right.value = 2;
    root3.right.right = new BinaryTreeNode();
    root3.right.right.value = 3;
    root3.right.right.right = new BinaryTreeNode();
    root3.right.right.right.value = 4;
    root3.right.right.right.right = new BinaryTreeNode();
    root3.right.right.right.right.value = 5;
    System.out.println("有1条路径上面的结点和为15：");
    findPath(root3, 15);
    System.out.println("没有路径上面的结点和为16");
    findPath(root3, 16);
}

运行结果

测试4：

public static void main(String[] args) {
    // 树中只有1个结点
    BinaryTreeNode root4 = new BinaryTreeNode();
    root4.value = 1;
    System.out.println("有1条路径上的结点和为1：");
    findPath(root4, 1);
    System.out.println("没有路径上的结点和为2");
    findPath(root4, 2);
}

运行结果

测试5：

public static void main(String[] args) {
    System.out.println("树中没有结点：");
    findPath(null, 0);
}

运行结果

来源：http://blog.csdn.net/derrantcm/article/details/46705853