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; }
