【IT笔试面试题整理】二叉树中和为某一值的路径--所有可能路径

【试题描述】

     You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree-it does not have to start at the root.

     输入一个整数和一棵二元树。从树的任意结点开始往下访问所经过的所有结点形成一条路径。

打印出和与输入整数相等的所有路径。

解题思路：

      一层一层的遍历，保存当前节点到根节点的完整路径，然后从当前节点向上扫描，如果找到了当前节点到某个节点的和等于给定值，则输出之。程序对每个节点都需要遍历一遍，还要扫描当前节点到根节点的路径，且需要保存每个节点到根节点的路径，所以时间复杂度为O（nlgn)，空间复杂度为O(nlgn)。

public static void findAllPath(Node head, int sum, ArrayList<Integer> buffer, int level)
    {
        if (head == null)
            return;
        int tmp = sum;
        buffer.add(head.value);
        for (int i = level; i >= 0; i--)
        {
            tmp -= buffer.get(i);
            if (tmp == 0)
                print(buffer, i, level);
        }

        ArrayList<Integer> c1 = (ArrayList<Integer>) buffer.clone();
        ArrayList<Integer> c2 = (ArrayList<Integer>) buffer.clone();

        findAllPath(head.left, sum, c1, level + 1);
        findAllPath(head.right, sum, c2, level + 1);
    }

    private static void print(ArrayList<Integer> buffer, int level, int i2)
    {
        System.out.print("找到路径为：");
        for (int i = level; i <= i2; i++)
            System.out.print(buffer.get(i) + " ");
        System.out.println();

    }