1.二叉树最大深度（104-易）
题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
思路：实现简单，直接使用递归和迭代求解。
代码实现：
// 递归
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
// 迭代
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
++level;
for (int i = 0; i < size; ++i) {
// 遍历本层，移除一个节点，并加入下一层对应的子节点
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return level;
}
2.平衡二叉树（110-易）
题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例：
输入：root = [3,9,20,null,null,15,7]
输出：true
思路：
- 递归（自顶向下）：递归最大深度，注意：我们要保证每颗子树都是平衡二叉树，所有主函数也要递归。
- 递归（自底向上）：在递归最大深度的是够进行判断，即只要子树出现不满足平衡二叉树的要求，直接返回false，推荐。
代码实现：
// 递归（自顶向下）
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return Math.abs(dfs(root.left) - dfs(root.right)) < 2
&& isBalanced(root.left)
&& isBalanced(root.right);
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(dfs(root.left), dfs(root.right)) + 1;
}
// 递归（自底向上）
private boolean ans = true;
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
dfs(root);
return ans;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
if (Math.abs(left - right) > 1) {
ans = false;
}
return Math.max(left, right) + 1;
}
3.二叉树最小深度（111-易）
题目描述：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例：
输入：root = [3,9,20,null,null,15,7]
输出：2
思路：
- 递归：与求深度相同（最大深度），但这里递归函数为根节点到叶子节点的最小深度。当只有一颗子树的情况，计算深度（基本逻辑）
- 迭代：迭代遍历层数就是我们的深度，只要在某层出现叶子节点，我们就返回层数（深度）。
代码实现：
// 递归
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
if (root.left == null || root.right == null) {
return left + right + 1;
}
return Math.min(left, right) + 1;
}
// 迭代
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
++level;
for (int i = 0; i < size; ++i) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return level;
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return 0;
}
总结：这种题目比较简单，其实深度延伸的题目还有很多，比如二叉树的直径（543），这种问题的都是根节点到叶子节点的问题。对于这种问题，有时自下向上的递归也是不错的选择
4.二叉树右视图（199-中）
题目描述：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例：
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
思路：使用广度优先搜索，只需要记录每一层的最后一个元素即可，左视图同理。
代码实现：
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; ++i) {
TreeNode node = queue.poll();
if (i == size - 1) {
ans.add(node.val);
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return ans;
}
延伸：T513找二叉树左下角的值，返回数组最后一个值即可。提供一个递归思路：
private int max = -1; //记录最大层数
private int res = 0;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 0);
return res;
}
private void dfs (TreeNode node, int level) {
if (node == null) return;
//递归层第一次大于当前最大层，即每层的第一个节点(更新)
if (level > max) {
max = level;
res = node.val;
}
dfs(node.left, level + 1);
dfs(node.right, level + 1);
}
5.二叉树每行的最大值（515-中）
题目描述：您需要在二叉树的每一行中找到最大的值。
示例：
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: [1, 3, 9]
思路：迭代实现比较简单，加一个变量更新每层的最大值即可。注意：确定完一层的最大值之后，不要忘记将max设置为最小值。
代码实现：
public List<Integer> largestValues(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> ans = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int max = Integer.MIN_VALUE;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; ++i) {
TreeNode node = queue.poll();
max = Math.max(max, node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
ans.add(max);
max = Integer.MIN_VALUE;
}
return ans;
}
补充一个DFS解法，我们在递归的过程将每层的最大值进行设置更新，代码实现：
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>();
//层级从0开始，result不需要考虑加1、减1的情况
dfs(root,0,result);
return result;
}
public void dfs(TreeNode root, int level, List<Integer> result) {
if (root == null) {
return;
}
if (result.size() == level) {
result.add(level , root.val);
}
int max = Math.max(result.get(level), root.val);
result.set(level, max);
dfs(root.left, level + 1, result);
dfs(root.right, level + 1, result);
}
补充：二叉搜索树的最小绝对值（T530），由于二叉搜索树中序遍历的有序性，所以最小值一定出现在中序遍历的相邻位置。可以使用递归和迭代求解。
代码实现：
// 递归
private TreeNode pre = null;
private int min = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
inorder(root);
return min;
}
private void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
if (pre != null) {
min = Math.min(min, root.val - pre.val);
}
pre = root;
inorder(root.right);
}
// 迭代
public int getMinimumDifference(TreeNode root) {
if (root == null) {
return 0;
}
TreeNode pre = null;
int min = Integer.MAX_VALUE;
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
if (pre != null) {
min = Math.min(min, node.val - pre.val);
}
pre = node;
cur = node.right;
}
return min;
}
网友评论