《剑指offer》第25题。

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

private class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

算法还是递归：二叉树的先序遍历。

public void findPath(BinaryTreeNode root, final int sum, 
                     LinkedList<Integer> path, int cur) {
    if (root == null) {
        return;
    }

    path.add(root.value);
    cur += root.value;

    if (root.left == null && root.right == null) {
        if (cur == sum) {
            System.out.println(path);
        }
    }

    if (root.left != null) {
        findPath(root.left, sum, path, cur);
    }
    if (root.right != null) {
        findPath(root.right, sum, path, cur);
    }
    // 与先序遍历的代码遥相呼应
    path.removeLast();
}

cur的初始值是0.

递归边界是叶子节点，而不是空节点，因为一个叶子节点的左右孩子都是空，这样可能会输出两次同一条路径。

这道题目的难点就在于路径这个概念。代码用LinkedList表示一个栈，用来记录路径上的节点。其中最后一行代码极易出错，我在学生时代就觉得不好理解。

代码是对二叉树进行先序遍历，其实就是对二叉树进行深度搜索。path是共享的，随着路径的加深需要变长，但是也需要按原路返回，所以整个程序结束后，path长度是0。

这道题的简单版本，判断是否存在和为某值的路径，返回布尔值。

class BinaryTreeNode {

    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;

    public BinaryTreeNode(int value) {
        this.value = value;
    }

    public BinaryTreeNode(int value, BinaryTreeNode left, BinaryTreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

public class BinaryTreePathSum {

    public boolean pathSum(BinaryTreeNode root, final int n) {
        if (root == null) {
            return false;
        }
        return find(root, n, 0);
    }

    private boolean find(BinaryTreeNode root, final int n, int sum) {
        if (root == null) {
            return n == sum;
        }
        sum += root.value;
        return find(root.left, n, sum) || find(root.right, n, sum);
    }

    public static void main(String[] args) {
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node6 = new BinaryTreeNode(6);

        BinaryTreeNode node2 = new BinaryTreeNode(2, node4, node5);
        BinaryTreeNode node3 = new BinaryTreeNode(3, null, node6);

        BinaryTreeNode node1 = new BinaryTreeNode(1, node2, node3);

        BinaryTreePathSum pathSum = new BinaryTreePathSum();
        for (int i = 1; i <=10 ; i++) {
            System.out.println(i+"\t"+ pathSum.pathSum(node1, i));
        }

    }
}

20191024 尝试了一种新的写法

    public boolean isFind(BinaryTreeNode root, final int target, int cur) {
        if (root == null) {
            return false;
        }

        cur += root.value;
        if (root.left == null && root.right == null) {
            return cur == target;
        }

        return  (root.left != null && isFind(root.left, target, cur)) || (root.right != null && isFind(root.right, target, cur));
    }