左叶子之和

发表于
本文字数： 1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，404. Sum Of Left Leaves

先看题目描述

大意就是给定一颗二叉树，让我们返回二叉树里所有的左叶子节点的和

算法和思路

这题很简单，从上往下使用递归计算就可以

以 root 为根的二叉树中所有的左叶子节点的和等于其左子树中所有的左叶子节点之和加上其右子树中所有的左叶子节点之和，为了实现要求，我们定义一个方法 dfs(root, flag)来实现该功能，当 root为空时，直接返回 0；若 root 为叶子节点时，不能直接返回其值，因为题目要的是左叶子节点，所以添加一个标志位 flag 标识该节点是其父节点的左子节点还是右子节点，用 flag = 1 表示为左子节点，flag = 0 表示为右子节点。所以若 root 为叶子节点且 flag = 1 时，则直接返回其值；若 root 为叶子节点且 flag = 0 时，则直接返回 0；若不是上述三种情况之一，则返回 dfs(root.left, 1) + dfs(root.right, 0)

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int flag) {
        if (root == null) return 0;
        if (flag == 1 && root.left == null && root.right == null) return root.val;
        return dfs(root.left, 1) + dfs(root.right, 0);
    }
}