LeetCode 404 左叶子之和

Posted on 2020-09-19  135 Views


题目链接

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

示例:

题解

第一想法就是递归调用直接加,即下面的递归方法。

官方题解

一个节点为「左叶子」节点,当且仅当它是某个节点的左子节点,并且它是一个叶子结点。因此我们可以考虑对整棵树进行遍历,当我们遍历到节点 node 时,如果它的左子节点是一个叶子结点,那么就将它的左子节点的值累加计入答案。

遍历整棵树的方法有深度优先搜索和广度优先搜索。

递归

复杂度分析:

  • 时间复杂度:O(n)
    其中 n 是树中的节点个数。
  • 空间复杂度:O(n)
class Solution {
    fun sumOfLeftLeaves(root: TreeNode?): Int {
        if (root == null) return 0
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right) +
                if (root.left != null && root.left!!.left == null && root.left!!.right == null) root.left!!.`val` else 0
    }
}

DFS

复杂度分析:

  • 时间复杂度:O(n)
    其中 n 是树中的节点个数。
  • 空间复杂度:O(n)
    空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下,树呈现链式结构,深度为 O(n),对应的空间复杂度也为 O(n)
class Solution {
    fun sumOfLeftLeaves(root: TreeNode?): Int {
        return if (root == null) 0 else dfs(root)
    }

    fun dfs(node: TreeNode?): Int {
        var ans: Int = 0
        if (node?.left != null)
            ans += if (isLeftNode(node.left)) node.left!!.`val` else dfs(node.left)
        if (node?.right != null)
            ans += dfs(node.right)
        return ans
    }

    fun isLeftNode(node: TreeNode?) = node?.left == null && node?.right == null

}

BFS

复杂度分析:

  • 时间复杂度:O(n)
    其中 n 是树中的节点个数。
  • 空间复杂度:O(n)
    空间复杂度与广度优先搜索使用的队列需要的容量相关,为 O(n)
class Solution {

    fun sumOfLeftLeaves(root: TreeNode?): Int {
        if (root == null) return 0
        var ans: Int = 0;
        val queue: Queue<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root);
        while (!queue.isEmpty()) {
            val node = queue.poll();
            if (node.left != null) {
                if (isLeftNode(node.left))
                    ans += node.left!!.`val`
                else
                    queue.offer(node.left)
            }
            if (node.right != null) {
                if (!isLeftNode(node.right))
                    queue.offer(node.right);
            }
        }
        return ans
    }

    fun isLeftNode(node: TreeNode?) = node?.left == null && node?.right == null

}

隐约雷鸣 阴霾天空 但盼风雨来 能留你在此