计算给定二叉树的所有左叶子之和。
示例：
3
/
9 20
/
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-left-leaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
二叉树的题目做多了，感觉到貌似一多半的题目，可以通过二叉树遍历来解决，前序/中序/后序/层序，总有一种适合你…的题目.
此题目中，是求左叶子之和，即为叶子节点 且 是其父节点的左子节点。
我们是否可以通过 二叉树遍历 解决呢？
答案是可以的。
虽然遍历到当前元素current时，我们无法判断current是其父节点的左还是右。 但是当我们访问 其父节点时，就可以来判断，其左子节点是不是 叶子节点啊。如果是叶子节点，不就是满足要求的节点吗.
所以我们遍历整个二叉树, 当遍历的节点的 左子节点不为空， 且左子节点为叶子节点时， 就累加其左子节点的值。
直到遍历完一整颗二叉树，我们也就求出了最终结果
遍历方式有很多 前序 / 中序 / 后序 / 层序， 迭代 或者 递归 都可以解决此问题。
正好就趁此题，来复习下，二叉树的各种遍历啦。
递归
我们可以轻松的使用递归，实现 前序/中序/后序遍历, 即dfs遍历. 这里我们只写一种前序遍历。
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return result;
if (root.left != null && root.left.left == null && root.left.right == null)
result += root.left.val;
sumOfLeftLeaves(root.left);
sumOfLeftLeaves(root.right);
return result;
}
|
迭代
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
/**
* 上边方法是递归，既然是dfs解决的问题
* 那么使用迭代应该同样可以解决问题
* <p>
* 顺便复习下，迭代二叉树遍历
*/
//迭代 中序遍历 因为写二叉搜索树的题目，用到中序遍历的情况特别多， 所以最熟悉的就是中序遍历 😳
public int sumOfLeftLeaves1(TreeNode root) {
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.left != null && root.left.left == null && root.left.right == null)
result += root.left.val;
root = root.right;
}
return result;
}
|
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
// 迭代 前序遍历 说实话，一下子没想起来，在稿纸上自己画一画先
public int sumOfLeftLeaves2(TreeNode root) {
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null && node.left.left == null && node.left.right == null)
result += node.left.val;
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return result;
}
|
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// 迭代 后序遍历
public int sumOfLeftLeaves3(TreeNode root) {
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode pre = null;
while (!stack.isEmpty()) {
TreeNode node = stack.peek();
if ((node.left == null && node.right == null) || (pre != null && (pre == node.left || pre == node.right))) {
// 叶子节点 或者 上一个访问的节点是此节点的子节点时 出栈
if (node.left != null && node.left.left == null && node.left.right == null)
result += node.left.val;
pre = node;
stack.pop();
} else {
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
}
return result;
}
|
层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 迭代 层序遍历
public int sumOfLeftLeaves4(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode node = queue.remove();
if (node.left != null && node.left.left == null && node.left.right == null)
result += node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
return result;
}
|
执行耗时
以上是 从 方法一 -> 方法五的执行耗时。
递归最快，后序遍历最慢，前序/中序/层序时间一致
按理来说，时间复杂度都是 O(N), 执行时间相差大这个问题，先遗留下，以后研究下，再单独写一篇文章解释这个问题。