重庆公司专业建站,收录查询站长工具,机房建设网站模板,销售类网站数据库的建设【C#刷题】| 作者 / Edison Zhou这是EdisonTalk的第292篇原创内容我们来用之前学到的数据结构知识来刷《剑指Offer》的一些核心题目#xff08;精选了其中30道题目#xff09;#xff0c;希望对你有帮助#xff01;本文题目为#xff1a;二叉树中和为某一值的路径。1题目介… 【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;Listint path new Listint();FindPath(root, expectedSum, path, ref currentSum);
}private static void FindPath(BinaryTreeNode root, int expectedSum, Listint 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开发
