本文共 5619 字,大约阅读时间需要 18 分钟。
【C#刷题】| 作者 / Edison Zhou
这是EdisonTalk的第292篇原创内容
我们来用之前学到的数据结构知识来刷《剑指Offer》的一些核心题目(精选了其中30+道题目),希望对你有帮助!本文题目为:二叉树中和为某一值的路径。
1题目介绍
题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。例如输入下图中二叉树和整数22,则打印出两条路径,第一条路径包含结点10、12,第二条路径包含结点10、5和7。
二叉树结点的自定义代码如下:
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)当用前序遍历的方式访问到某一结点时,我们把该结点添加到路径上,并累加该结点的值。
(2)如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数,则当前的路径符合要求,我们把它打印出来。如果当前结点不是叶结点,则继续访问它的子结点。
(3)当前结点访问结束后,递归函数将自动回到它的父结点。这里要注意的是:在函数退出之前要在路径上删除当前结点并减去当前结点的值,以确保返回父结点时路径刚好是从根结点到父结点的路径。
代码实现:
public static void FindPath(BinaryTreeNode root, int expectedSum){ if (root == null) { return; } int currentSum = 0; List path = new List (); FindPath(root, expectedSum, path, ref currentSum);}private static void FindPath(BinaryTreeNode root, int expectedSum, List 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单元测试
测试辅助方法:
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); }}
单元测试用例:
// 10// / \// 5 12// /\ // 4 7 // 有两条路径上的结点和为22public 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 // 没有路径上的结点和为15public 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// 有一条路径上面的结点和为15public 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// 没有路径上面的结点和为16public 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);}
测试结果:
测试的结果情况如下图:
Ref参考资料
何海涛,《剑指Offer》
后台回复:剑指offer,即可获得pdf下载链接哟!
????扫码关注EdisonTalk
设为星标,不再失联!
往期推文合集:
成都新鲜坑位:
转载地址:http://zdkdi.baihongyu.com/