LeetCode 404. 左叶子之和

Categories:

题目描述
思路分析
1. 解法一：DFS 递归（推荐）
相似题目

题目描述

✅ 404. 左叶子之和

思路分析

解法一：DFS 递归（推荐）

核心思路：

如果当前节点的左子节点是叶子，则累加其值。

否则递归遍历左子树。

右子树始终递归遍历，避免漏算。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，其中 h 表示树高（递归栈）。

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int sum = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) {
            sum += root.left.val;
        } else {
            sum += sumOfLeftLeaves(root.left);
        }

        sum += sumOfLeftLeaves(root.right);
        return sum;
    }
}

func sumOfLeftLeaves(root *TreeNode) int {
	if root == nil {
		return 0
	}

	sum := 0
	if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
		sum += root.Left.Val
	} else {
		sum += sumOfLeftLeaves(root.Left)
	}

	sum += sumOfLeftLeaves(root.Right)
	return sum
}

相似题目

题目	难度	考察点
404. 左叶子之和	简单	DFS
113. 路径总和 II	中等	DFS、回溯
112. 路径总和	简单	DFS
515. 在每个树行中找最大值	中等	BFS
437. 路径总和 III	中等	DFS、前缀和
543. 二叉树的直径	简单	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/28113436