纵有疾风起
人生不言弃

剑指Offer面试题:23.二叉树中和为某一值的路径


一、题目:二叉树中和为某一值的路径

题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。例如输入下图中二叉树和整数22,则打印出两条路径,第一条路径包含结点10、12,第二条路径包含结点10、5和7。

剑指Offer面试题:23.二叉树中和为某一值的路径插图

  二叉树结点的定义如下:

    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 核心步骤

  首先,通过下图了解遍历上图中的二叉树的过程:

剑指Offer面试题:23.二叉树中和为某一值的路径插图(1)

  通过上图可以总结出规律:

  (1)当用前序遍历的方式访问到某一结点时,我们把该结点添加到路径上,并累加该结点的值。

  (2)如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数,则当前的路径符合要求,我们把它打印出来。如果当前结点不是叶结点,则继续访问它的子结点。

  (3)当前结点访问结束后,递归函数将自动回到它的父结点。这里要注意的是:在函数退出之前要在路径上删除当前结点并减去当前结点的值,以确保返回父结点时路径刚好是从根结点到父结点的路径。

2.2 代码实现

    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);        // 如果是叶结点,并且路径上结点的和等于输入的值        // 打印出这条路径        bool isLeaf = root.leftChild == null && root.rightChild == null;        if (isLeaf && currentSum == expectedSum)        {            foreach (int data in path)            {                Console.Write("{0}\t", data);            }            Console.WriteLine();        }        // 如果不是叶结点,则遍历它的子结点        if (root.leftChild != null)        {            FindPath(root.leftChild, expectedSum, path, ref currentSum);        }        if (root.rightChild != null)        {            FindPath(root.rightChild, expectedSum, path, ref currentSum);        }        // 在返回到父结点之前,在路径上删除当前结点,        // 并在currentSum中减去当前结点的值        path.Remove(root.Data);        currentSum -= root.Data;    }

三、单元测试

3.1 测试用例

  (1)辅助方法的封装

剑指Offer面试题:23.二叉树中和为某一值的路径插图(2)

    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)功能、特殊输入测试

    //            10    //         /      \    //        5        12    //       /\            //      4  7         // 有两条路径上的结点和为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         // 没有路径上的结点和为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    // 有一条路径上面的结点和为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    // 没有路径上面的结点和为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个结点    public static void Test5()    {        BinaryTreeNode node1 = new BinaryTreeNode(1);        Console.WriteLine("One paths should be found in Test5.");        TestPortal("Test5", node1, 1);        ClearUpTreeNode(node1);    }    // 树中没有结点    public static void Test6()    {        Console.WriteLine("No paths should be found in Test6.");        TestPortal("Test6", null, 0);    }

3.2 测试结果

剑指Offer面试题:23.二叉树中和为某一值的路径插图(4)

 

文章转载于:https://www.cnblogs.com/edisonchou/p/4787736.html

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » 剑指Offer面试题:23.二叉树中和为某一值的路径

分享到: 生成海报
avatar

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活