劍指Offer面試題：23.二叉樹中和為某一值的路徑

題目：輸入一棵二叉樹和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。例如輸入下圖中二叉樹和整數(shù)22，則打印出兩條路徑，第一條路徑包含結(jié)點(diǎn)10、12，第二條路徑包含結(jié)點(diǎn)10、5和7。

一、題目：二叉樹中和為某一值的路徑

題目：輸入一棵二叉樹和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。例如輸入下圖中二叉樹和整數(shù)22，則打印出兩條路徑，第一條路徑包含結(jié)點(diǎn)10、12，第二條路徑包含結(jié)點(diǎn)10、5和7。

　　二叉樹結(jié)點(diǎn)的定義如下：

    public class BinaryTreeNode
    {
        public int Data { get; set; }
        public BinaryTreeNode leftChild { get; set; }
        public BinaryTreeNode rightChild { get; set; }

        public BinaryTreeNode(int data)
        {
            this.Data = data;
        }

        public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right)
        {
            this.Data = data;
            this.leftChild = left;
            this.rightChild = right;
        }
    }

二、解題思路

2.1 核心步驟

　　首先，通過下圖了解遍歷上圖中的二叉樹的過程：

　　通過上圖可以總結(jié)出規(guī)律：

　　（1）當(dāng)用前序遍歷的方式訪問到某一結(jié)點(diǎn)時(shí)，我們把該結(jié)點(diǎn)添加到路徑上，并累加該結(jié)點(diǎn)的值。

　　（2）如果該結(jié)點(diǎn)為葉結(jié)點(diǎn)并且路徑中結(jié)點(diǎn)值的和剛好等于輸入的整數(shù)，則當(dāng)前的路徑符合要求，我們把它打印出來。如果當(dāng)前結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則繼續(xù)訪問它的子結(jié)點(diǎn)。

　　（3）當(dāng)前結(jié)點(diǎn)訪問結(jié)束后，遞歸函數(shù)將自動(dòng)回到它的父結(jié)點(diǎn)。這里要注意的是：在函數(shù)退出之前要在路徑上刪除當(dāng)前結(jié)點(diǎn)并減去當(dāng)前結(jié)點(diǎn)的值，以確保返回父結(jié)點(diǎn)時(shí)路徑剛好是從根結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑。

2.2 代碼實(shí)現(xiàn)

    public static void FindPath(BinaryTreeNode root, int expectedSum)
    {
        if (root == null)
        {
            return;
        }

        int currentSum = 0;
        List<int> path = new List<int>();
        FindPath(root, expectedSum, path, ref currentSum);
    }

    private static void FindPath(BinaryTreeNode root, int expectedSum, List<int> path, ref int currentSum)
    {
        currentSum += root.Data;
        path.Add(root.Data);
        // 如果是葉結(jié)點(diǎn)，并且路徑上結(jié)點(diǎn)的和等于輸入的值
        // 打印出這條路徑
        bool isLeaf = root.leftChild == null && root.rightChild == null;
        if (isLeaf && currentSum == expectedSum)
        {
            foreach (int data in path)
            {
                Console.Write("{0}\t", data);
            }
            Console.WriteLine();
        }

        // 如果不是葉結(jié)點(diǎn)，則遍歷它的子結(jié)點(diǎn)
        if (root.leftChild != null)
        {
            FindPath(root.leftChild, expectedSum, path, ref currentSum);
        }

        if (root.rightChild != null)
        {
            FindPath(root.rightChild, expectedSum, path, ref currentSum);
        }

        // 在返回到父結(jié)點(diǎn)之前，在路徑上刪除當(dāng)前結(jié)點(diǎn)，
        // 并在currentSum中減去當(dāng)前結(jié)點(diǎn)的值
        path.Remove(root.Data);
        currentSum -= root.Data;
    }

三、單元測(cè)試

3.1 測(cè)試用例

　　（1）輔助方法的封裝

    private static void TestPortal(string testName, BinaryTreeNode root, int expectedSum)
    {
        if (!string.IsNullOrEmpty(testName))
        {
            Console.WriteLine("{0} begins:", testName);
        }

        FindPath(root, expectedSum);

        Console.WriteLine();
    }

    private static void SetSubTreeNode(BinaryTreeNode root, BinaryTreeNode lChild, BinaryTreeNode rChild)
    {
        if (root == null)
        {
            return;
        }

        root.leftChild = lChild;
        root.rightChild = rChild;
    }

    private static void ClearUpTreeNode(BinaryTreeNode root)
    {
        if (root != null)
        {
            BinaryTreeNode left = root.leftChild;
            BinaryTreeNode right = root.rightChild;

            root = null;

            ClearUpTreeNode(left);
            ClearUpTreeNode(right);
        }
    }

View Code

　　（2）功能、特殊輸入測(cè)試

    //            10
    //         /      \
    //        5        12
    //       /\        
    //      4  7     
    // 有兩條路徑上的結(jié)點(diǎn)和為22
    public static void Test1()
    {
        BinaryTreeNode node10 = new BinaryTreeNode(10);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node12 = new BinaryTreeNode(12);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node7 = new BinaryTreeNode(7);

        SetSubTreeNode(node10, node5, node12);
        SetSubTreeNode(node5, node4, node7);

        Console.WriteLine("Two paths should be found in Test1.");
        TestPortal("Test1", node10, 22);

        ClearUpTreeNode(node10);
    }

    //            10
    //         /      \
    //        5        12
    //       /\        
    //      4  7     
    // 沒有路徑上的結(jié)點(diǎn)和為15
    public static void Test2()
    {
        BinaryTreeNode node10 = new BinaryTreeNode(10);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node12 = new BinaryTreeNode(12);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node7 = new BinaryTreeNode(7);

        SetSubTreeNode(node10, node5, node12);
        SetSubTreeNode(node5, node4, node7);

        Console.WriteLine("No paths should be found in Test2.");
        TestPortal("Test2", node10, 15);

        ClearUpTreeNode(node10);
    }

    //               5
    //              /
    //             4
    //            /
    //           3
    //          /
    //         2
    //        /
    //       1
    // 有一條路徑上面的結(jié)點(diǎn)和為15
    public static void Test3()
    {
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node1 = new BinaryTreeNode(1);

        node5.leftChild = node4;
        node4.leftChild = node3;
        node3.leftChild = node2;
        node2.leftChild = node1;

        Console.WriteLine("One path should be found in Test3.");
        TestPortal("Test3", node5, 15);

        ClearUpTreeNode(node5);
    }

    // 1
    //  \
    //   2
    //    \
    //     3
    //      \
    //       4
    //        \
    //         5
    // 沒有路徑上面的結(jié)點(diǎn)和為16
    public static void Test4()
    {
        BinaryTreeNode node1 = new BinaryTreeNode(1);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node5 = new BinaryTreeNode(5);

        node1.leftChild = node2;
        node2.leftChild = node3;
        node3.leftChild = node4;
        node4.leftChild = node5;

        Console.WriteLine("No paths should be found in Test4.");
        TestPortal("Test4", node1, 16);

        ClearUpTreeNode(node1);
    }

    // 樹中只有1個(gè)結(jié)點(diǎn)
    public static void Test5()
    {
        BinaryTreeNode node1 = new BinaryTreeNode(1);

        Console.WriteLine("One paths should be found in Test5.");
        TestPortal("Test5", node1, 1);

        ClearUpTreeNode(node1);
    }

    // 樹中沒有結(jié)點(diǎn)
    public static void Test6()
    {
        Console.WriteLine("No paths should be found in Test6.");
        TestPortal("Test6", null, 0);
    }