C#LeetCode刷题之#404-左叶子之和​​​​​​​​​​​​​​(Sum of Left Leaves)

C#LeetCode刷题之#404-左叶子之和​​​​​​​​​​​​​​(Sum of Left Leaves)

问题

计算给定二叉树的所有左叶子之和。

      3
     / \
   9  20
  /       \
15       7

在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

Find the sum of all left leaves in a given binary tree.

      3
     / \
   9  20
  /       \
15       7

There 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

分析:

显而易见,以上算法的时间复杂度为: O(n)​ 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4084

发表评论

登录后才能评论