LeetCode题目——左叶子之和(sum-of-left-leaves)
计算给定二叉树的所有左叶子之和。
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
思路
本题的难点在于，首先要知道
- 什么是叶子节点 ?
- 如何判断一个节点是不是左叶子节点 ?
第一个问题，
如果一个节点没有左右孩子，那么这个节点就是叶子节点。或者一棵树当中没有子结点（即度为0）的结点称为叶子结点，简称“叶子”。
我们看一下节点的代码TreeNode，如下
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
很明显节点自己就可以判断它的左右孩子是不是空。
第二个问题,
如何判断一个节点是不是左叶子节点，这个只能由它的父亲来判断。
深圳优先搜索
package sum_of_left_leaves;
import common.TreeNode;
//404. 左叶子之和
public 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;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
TreeNode root_l = new TreeNode(9);
TreeNode root_r = new TreeNode(20);
TreeNode root_rl = new TreeNode(15);
TreeNode root_rr = new TreeNode(7);
root.left = root_l;
root.right = root_r;
root_r.left = root_rl;
root_r.right = root_rr;
Solution s =new Solution();
int sum = s.sumOfLeftLeaves(root);
System.out.println(sum);
}
}
广度优先搜索
package sum_of_left_leaves;
import java.util.LinkedList;
import java.util.Queue;
import common.TreeNode;
class Solution2 {
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()) {
TreeNode node = queue.poll();
if (node.left != null) {
if (isLeafNode(node.left)) {
ans += node.left.val;
} else {
queue.offer(node.left);
}
}
if (node.right != null) {
if (!isLeafNode(node.right)) {
queue.offer(node.right);
}
}
}
return ans;
}
//判断当前节点是否是叶子节点
public boolean isLeafNode(TreeNode node) {
return node.left == null && node.right == null;
}
}
测试数据
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
TreeNode root_l = new TreeNode(9);
TreeNode root_r = new TreeNode(20);
TreeNode root_rl = new TreeNode(15);
TreeNode root_rr = new TreeNode(7);
root.left = root_l;
root.right = root_r;
root_r.left = root_rl;
root_r.right = root_rr;
Solution s =new Solution();
int sum = s.sumOfLeftLeaves(root);
System.out.println(sum);
}
输出24
一个函数
可以看到，上面的代码都是用了三个函数，那可以用一个函数搞定吗。也是可以的。
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int sum = 0;
if (root.left != null && root.left.left == root.left.right) {
sum = root.left.val;
}
return sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
}
TreeNode树节点的代码
package common;
import java.util.LinkedList;
import java.util.Queue;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}