二叉樹中和為某一值的路徑

題目：輸入一棵二叉樹和一個整數(shù)， 打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。

二叉樹結(jié)點的定義：

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

解題思路：

由于路徑是從根結(jié)點出發(fā)到葉結(jié)點， 也就是說路徑總是以根結(jié)點為起始點，因此我們首先需要遍歷根結(jié)點。在樹的前序、中序、后序三種遍歷方式中，只有前序遍歷是首先訪問根結(jié)點的。

當用前序遍歷的方式訪問到某一結(jié)點時， 我們把該結(jié)點添加到路徑上，并累加該結(jié)點的值。如果該結(jié)點為葉結(jié)點并且路徑中結(jié)點值的和剛好等于輸入的整數(shù)， 則當前的路徑符合要求，我們把它打印出來。如果當前結(jié)點不是葉結(jié)點，則繼續(xù)訪問它的子結(jié)點。當前結(jié)點訪問結(jié)束后，遞歸函數(shù)將自動回到它的父結(jié)點。因此我們在函數(shù)退出之前要在路徑上刪除當前結(jié)點并減去當前結(jié)點的值，以確保返回父結(jié)點時路徑剛好是從根結(jié)點到父結(jié)點的路徑。

不難看出保存路徑的數(shù)據(jù)結(jié)構(gòu)實際上是一個枝， 因為路徑要與遞歸調(diào)用狀態(tài)一致， 而遞歸調(diào)用的本質(zhì)就是一個壓棧和出棧的過程。

代碼實現(xiàn)：

public class Test25 {
    /**
     * 二叉樹的樹結(jié)點
     */
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }
    /**
     * 輸入一棵二叉樹和一個整數(shù)， 打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。
     * 從樹的根結(jié)點開始往下一直到葉銷點所經(jīng)過的結(jié)點形成一條路徑。
     *
     * @param root        樹的根結(jié)點
     * @param expectedSum 要求的路徑和
     */
    public static void findPath(BinaryTreeNode root, int expectedSum) {
        // 創(chuàng)建一個鏈表，用于存放根結(jié)點到當前處理結(jié)點的所經(jīng)過的結(jié)點
        List<Integer> list = new ArrayList<>();
        // 如果根結(jié)點不為空，就調(diào)用輔助處理方法
        if (root != null) {
            findPath(root, 0, expectedSum, list);
        }
    }
    /**
     * @param root        當前要處理的結(jié)點
     * @param curSum      當前記錄的和（還未加上當前結(jié)點的值）
     * @param expectedSum 要求的路徑和
     * @param result      根結(jié)點到當前處理結(jié)點的所經(jīng)過的結(jié)點，（還未包括當前結(jié)點）
     */
    public static void findPath(BinaryTreeNode root, int curSum, int expectedSum, List<Integer> result) {
        // 如果結(jié)點不為空就進行處理
        if (root != null) {
            // 加上當前結(jié)點的值
            curSum += root.value;
            // 將當前結(jié)點入隊
            result.add(root.value);
            // 如果當前結(jié)點的值小于期望的和
            if (curSum < expectedSum) {
                // 遞歸處理左子樹
                findPath(root.left, curSum, expectedSum, result);
                // 遞歸處理右子樹
                findPath(root.right, curSum, expectedSum, result);
            }
            // 如果當前和與期望的和相等
            else if (curSum == expectedSum) {
                // 當前結(jié)點是葉結(jié)點，則輸出結(jié)果
                if (root.left == null && root.right == null) {
                    System.out.println(result);
                }
            }
            // 移除當前結(jié)點
            result.remove(result.size() - 1);
        }
    }
    public static void main(String[] args) {
        //            10
        //         /      \
        //        5        12
        //       /\
        //      4  7
        BinaryTreeNode root = new BinaryTreeNode();
        root.value = 10;
        root.left = new BinaryTreeNode();
        root.left.value = 5;
        root.left.left = new BinaryTreeNode();
        root.left.left.value = 4;
        root.left.right = new BinaryTreeNode();
        root.left.right.value = 7;
        root.right = new BinaryTreeNode();
        root.right.value = 12;
        // 有兩條路徑上的結(jié)點和為22
        System.out.println("findPath(root, 22);");
        findPath(root, 22);
        // 沒有路徑上的結(jié)點和為15
        System.out.println("findPath(root, 15);");
        findPath(root, 15);
        // 有一條路徑上的結(jié)點和為19
        System.out.println("findPath(root, 19);");
        findPath(root, 19);
        //               5
        //              /
        //             4
        //            /
        //           3
        //          /
        //         2
        //        /
        //       1
        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;
        // 有一條路徑上面的結(jié)點和為15
        System.out.println("findPath(root2, 15);");
        findPath(root2, 15);
        // 沒有路徑上面的結(jié)點和為16
        System.out.println("findPath(root2, 16);");
        findPath(root2, 16);
        // 1
        //  \
        //   2
        //    \
        //     3
        //      \
        //       4
        //        \
        //         5
        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;
        // 有一條路徑上面的結(jié)點和為15
        System.out.println("findPath(root3, 15);");
        findPath(root3, 15);
        // 沒有路徑上面的結(jié)點和為16
        System.out.println("findPath(root3, 16);");
        findPath(root3, 16);
        // 樹中只有1個結(jié)點
        BinaryTreeNode root4 = new BinaryTreeNode();
        root4.value = 1;
        // 有一條路徑上面的結(jié)點和為1
        System.out.println("findPath(root4, 1);");
        findPath(root4, 1);
        // 沒有路徑上面的結(jié)點和為2
        System.out.println("findPath(root4, 2);");
        findPath(root4, 2);
        // 樹中沒有結(jié)點
        System.out.println("findPath(null, 0);");
        findPath(null, 0);
    }
}

運行結(jié)果：

http://wiki.jikexueyuan.com/project/for-offer/images/32.png" alt="" />