categories: [Blog,Algorithm]

404. 左叶子之和

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

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

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

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

深度优先搜索

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public int sumOfLeftLeaves(TreeNode root) {
  12.         return root != null ? dfs(root) : 0;
  13.     }
  15.     public int dfs(TreeNode node) {
  16.         int ans = 0;
  17.         if (node.left != null) {
  18.             ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
  19.         }
  20.         if (node.right != null && !isLeafNode(node.right)) {
  21.             ans += dfs(node.right);
  22.         }
  23.         return ans;
  24.     }
  26.     public boolean isLeafNode(TreeNode node) {
  27.         return node.left == null && node.right == null;
  28.     }
  30. // 作者：LeetCode-Solution
  31. // 链接：https://leetcode-cn.com/problems/sum-of-left-leaves/solution/zuo-xie-zi-zhi-he-by-leetcode-solution/
  32. }

广度优先遍历

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public int sumOfLeftLeaves(TreeNode root) {
  12.         if (root == null) {
  13.             return 0;
  14.         }
  16.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  17.         queue.offer(root);
  18.         int ans = 0;
  19.         while (!queue.isEmpty()) {
  20.             TreeNode node = queue.poll();
  21.             if (node.left != null) {
  22.                 if (isLeafNode(node.left)) {
  23.                     ans += node.left.val;
  24.                 } else {
  25.                     queue.offer(node.left);
  26.                 }
  27.             }
  28.             if (node.right != null) {
  29.                 if (!isLeafNode(node.right)) {
  30.                     queue.offer(node.right);
  31.                 }
  32.             }
  33.         }
  34.         return ans;
  35.     }
  37.     public boolean isLeafNode(TreeNode node) {
  38.         return node.left == null && node.right == null;
  39.     }
  41. // 作者：LeetCode-Solution
  42. // 链接：https://leetcode-cn.com/problems/sum-of-left-leaves/solution/zuo-xie-zi-zhi-he-by-leetcode-solution/
  43. }