【每日算法Day 28】二叉树基础3
更多基于二叉树遍历的应用，状态值的自顶向下和自底向上的传递的异同，同一问题有递归与迭代写法，递归写法通过参数和返回值传递，迭代写法通过向栈或队列中压入节点和状态值的封装对象来传递。
# LeetCode 129. 求根到叶子节点数字之和 (opens new window)
# 题目描述
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
# 示例
输入: [1,2,3]
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
2
3
4
5
6
7
8
9
# 解题思路
同样地，有递归写法和非递归写法。递归写法在递归时传递截至当前节点的路径代表的数字，使用一个成员变量保存全局的数字之和，在叶子节点处把当前路径的数字加到成员变量上：
public class No129_SumRootToLeafNumbers {
int total=0;
public int sumNumbers(TreeNode root) {
traversal(root,0);
return total;
}
private void traversal(TreeNode current, int sum) {
if (current != null) {
sum=sum*10+current.val;
if (current.left == null && current.right == null) {
total += sum;
} else {
if (current.left!=null)
traversal(current.left,sum);
if (current.right!=null)
traversal(current.right,sum);
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
非递归写法的话，选择基于栈的前序遍历和基于队列的层次遍历都可以，不过需要使用一个内部类封装节点和当前节点前路径的值。实际LeetCode运行要比递归的慢一些。
public class No129_SumRootToLeafNumbers {
public int sumNumbers(TreeNode root) {
if (root==null) return 0;
int total=0;
Deque<NodeWithSum> stack = new LinkedList<>();
stack.push(new NodeWithSum(0,root));
while (!stack.isEmpty()) {
NodeWithSum current=stack.pop();
int sum=current.lastSum *10+current.node.val;
if (current.node.left == null && current.node.right == null) {
total += sum;
} else {
if (current.node.right!=null)
stack.push(new NodeWithSum(sum,current.node.right));
if (current.node.left != null)
stack.push(new NodeWithSum(sum,current.node.left));
}
}
return total;
}
private class NodeWithSum {
int lastSum;
TreeNode node;
public NodeWithSum(int lastSum, TreeNode node) {
this.lastSum = lastSum;
this.node = node;
}
}
}
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
28
29
30
31
# LeetCode 111. 二叉树的最小深度 (opens new window)
# 题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
# 示例
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
2
3
4
5
6
7
8
# 解题思路
看到最小深度最先想到的自然是层次遍历，一旦发现叶子节点就可以返回深度值了。也可以使用前序/中序/后序遍历，虽然理论时间空间复杂度相同都为O(n)，不过后者基于DFS，可能在找到最小深度的路径前会多进行一些遍历。
public int minDepth(TreeNode root) {
if (root==null) return 0;
int depth=1;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size=queue.size();
while (size > 0) {
TreeNode current=queue.poll();
if (current.left == null && current.right == null) {
return depth;
} else {
if (current.left!=null)
queue.offer(current.left);
if (current.right!=null)
queue.offer(current.right);
}
size--;
}
depth++;
}
return depth;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
104题二叉树的最大深度也非常类似，只是遍历完所有层后才返回最终的深度。
public int maxDepth(TreeNode root) {
if (root==null) return 0;
int depth=1;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size=queue.size();
while (size > 0) {
TreeNode current=queue.poll();
//这里都不需要判断是否为根节点了
if (current.left!=null)
queue.offer(current.left);
if (current.right!=null)
queue.offer(current.right);
size--;
}
depth++;
}
//由于最后一层的根节点遍历完之后还做了一次depth++，所以需要减一
return depth-1;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# LeetCode 110. 平衡二叉树 (opens new window)
# 题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
# 示例
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
2
3
4
5
6
7
8
# 解题思路
这一题显然是要遍历完整棵树没有不符合要求的子树才返回true。由于“子树的高度”是由下而上确定的，而不是自顶向下传递的，所以遍历方法不会传递深度，而是返回该节点本身的高度（为空节点时高度为0，为叶子节点时高度为1，否则高度为子树的最大高度+1）。发现两个子树的高度差超过1时该树就不是高度平衡的二叉树。
由于自底向上传递信息时递归更方便写一些，所以就使用了递归写法，这时需要设置一个成员变量。这种方法的缺点是在发现不满足平衡树要求时仍需要继续递归遍历完，不能立刻返回判断。
public class No110_BalancedBinaryTree {
boolean isBalanced=true;
public boolean isBalanced(TreeNode root) {
traversal(root);
return isBalanced;
}
private int traversal(TreeNode root) {
if (root==null) return 0;
if (root.left==null&&root.right==null) return 1;
int leftHeight=traversal(root.left);
int rightHeight=traversal(root.right);
if (Math.abs(leftHeight-rightHeight)>1)
isBalanced=false;
return Math.max(leftHeight,rightHeight)+1;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17