【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<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單元測試

測試輔助方法：

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 // 有兩條路徑上的結點和為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); }

測試結果：

測試的結果情況如下圖：

Ref參考資料

何海濤，《劍指Offer》

后臺回復：劍指offer，即可獲得pdf下載鏈接喲！

????掃碼關注EdisonTalk

設為星標，不再失聯！

往期推文合集：2020年上半年推文合集

成都新鮮坑位：喜鵲生活招聘.NET開發

總結

以上是生活随笔為你收集整理的C#刷剑指Offer | 二叉树中和为某一值的路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。