
问题
计算给定二叉树的所有左叶子之和。
3
/ \
9 20
/ \
15 7在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
Find the sum of all left leaves in a given binary tree.
3
/ \
9 20
/ \
15 7There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
示例
public class Program { public static void Main(string[] args) { var root = new TreeNode(1) { left = new TreeNode(5) }; var res = SumOfLeftLeaves(root); Console.WriteLine(res); Console.ReadKey(); } public static int SumOfLeftLeaves(TreeNode root) { var sum = 0; PreOrder(root, ref sum, false); return sum; } public static void PreOrder(TreeNode root, ref int sum, bool left) { if(root == null) return; if(left && root.left == null && root.right == null) sum += root.val; PreOrder(root?.left, ref sum, true); PreOrder(root?.right, ref sum, false); } public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } }
以上给出1种算法实现,以下是这个案例的输出结果:
5
分析:
显而易见,以上算法的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4084。