
问题
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
示例
public class Program { public static void Main(string[] args) { var root = new TreeNode(1) { left = new TreeNode(2) { right = new TreeNode(5) }, right = new TreeNode(3) }; var res = HasPathSum(root, 4); Console.WriteLine(res); res = HasPathSum2(root, 5); Console.WriteLine(res); Console.ReadKey(); } public static bool HasPathSum(TreeNode root, int sum) { if(root == null) return false; var res = false; PathSum(root, root.val, sum, ref res); return res; } public static void PathSum(TreeNode root, int cursum, int sum, ref bool has) { if(root.left == null && root.right == null && cursum == sum) { //若左右子节点都为空,本次路径结束 has = true; return; } if(root.left != null) //若左子节点不为空,则将左子节点和当前和累加之后参与下次递归 PathSum(root.left, cursum + root.left.val, sum, ref has); if(root.right != null) //若右子节点不为空,则将右子节点和当前和累加之后参与下次递归 PathSum(root.right, cursum + root.right.val, sum, ref has); } public static bool HasPathSum2(TreeNode root, int sum) { //边界判定 if(root == null) return false; //如果 sum 等于当前节点的值,并且为叶子节点时,返回 true if(root.val == sum && root.left == null && root.right == null) return true; //每次传递时用 sum - 当前值 return HasPathSum2(root.left, sum - root.val) || HasPathSum2(root.right, sum - root.val); } public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } }
以上给出2种算法实现,以下是这个案例的输出结果:
True False
分析:
显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4078。