404. 左叶子之和


404. 左叶子之和

难度简单 286
计算给定二叉树的所有左叶子之和。
示例:
    3
   /
  9  20
    /  
   15   7

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

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

遍历整棵树的方法有深度优先搜索和广度优先搜索,下面分别给出了实现代码。

深度优先搜索

/**
 * 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 root != null ? dfs(root) : 0;
    }

    public int dfs(TreeNode node) {
        int ans = 0;
        if (node.left != null) {
            ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
        }
        if (node.right != null && !isLeafNode(node.right)) {
            ans += dfs(node.right);
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }

// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/sum-of-left-leaves/solution/zuo-xie-zi-zhi-he-by-leetcode-solution/
}

广度优先遍历

/**
 * 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) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) &#123;
            TreeNode node = queue.poll();
            if (node.left != null) &#123;
                if (isLeafNode(node.left)) &#123;
                    ans += node.left.val;
                &#125; else &#123;
                    queue.offer(node.left);
                &#125;
            &#125;
            if (node.right != null) &#123;
                if (!isLeafNode(node.right)) &#123;
                    queue.offer(node.right);
                &#125;
            &#125;
        &#125;
        return ans;
    &#125;

    public boolean isLeafNode(TreeNode node) &#123;
        return node.left == null && node.right == null;
    &#125;

// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/sum-of-left-leaves/solution/zuo-xie-zi-zhi-he-by-leetcode-solution/
&#125;

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
剑指 Offer 54. 二叉搜索树的第k大节点 剑指 Offer 54. 二叉搜索树的第k大节点
剑指 Offer 54. 二叉搜索树的第 k 大节点难度简单 122给定一棵二叉搜索树,请找出其中第 k 大的节点。 示例 1:输入: root = [3,1,4,null,2], k = 1   3  /  1   4     2输出:
2021-03-01 future
下一篇 
680. 验证回文字符串 Ⅱ 680. 验证回文字符串 Ⅱ
680. 验证回文字符串 Ⅱ难度简单 324给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。示例 1:输入: “aba”输出: True 示例 2:输入: “abca”输出: True解释: 你可以删除 c 字符。 cl
2021-03-01 future
  目录