[算法学习]打印树的路径

算法

问题描述： 输入一个整数sum和一棵二叉树，打印出二叉树中结点和为sum的所有路径。 （路径：从根结点往下一直到叶结点形成的一条路径。）

解法与分析：

  1. 需要从树上的根结点遍历到叶子结点，其中需要累加经过结点的值。
  2. 当累加到叶子结点时，比较累加结点值和sum的值，如果相等，打印出路径；如果不相等，返回到上一层，寻找其他叶子结点。
  3. 需要保存结点路径，还可以返回到上一个结点，可以选择用栈来保存经过结点。
  4. 可以使用递归来描述这个解法。

参考代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * 树结点
 */
static class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val)
    {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * 寻找路径
 */
public static void findPath(TreeNode root, int sum)
{
    if (root == null) return;
    Stack<Integer> paths = new Stack<Integer>();
    findPath(root, paths, sum, 0);
}

/**
 * 递归寻找路径
 */
private static void findPath(TreeNode root, Stack<Integer> paths, int sum,int currentSum)
{
    currentSum += root.val;
    boolean isLeaf = root.left == null && root.right == null;
    paths.push(root.val);
    if (isLeaf && currentSum == sum)
    {
        printPath(paths);
    }
    if (root.left != null)
    {
        findPath(root.left, paths, sum, currentSum);
    }
    if (root.right != null)
    {
        findPath(root.right, paths, sum, currentSum);
    }
    paths.pop();
}

/**
 * 打印路径
 */
static void printPath(Stack<Integer> paths)
{
    if (paths.isEmpty()) return;
    for (Integer item : paths)
    {
        System.out.print(item + " - ");
    }
    System.out.println();
}