目录

• 一、二叉树的最小深度
• • 思路一：深度优先搜索
  • 代码实现
  • 思路二：广度优先搜索
  • 代码实现
• 二、二叉树的所有路径
• • 思路一：递归法
  • 代码实现
  • 思路二：迭代法
• 三、翻转二叉树
• • 思路一：递归法
  • 代码实现
  • 思路二：迭代法
  • 代码实现

一、二叉树的最小深度

思路一：深度优先搜索

我们这里使用后序遍历的方式！
对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点的深度，就将大问题转化成小问题。
确定终止条件
终止条件也是遇到空节点返回0，表示当前节点的高度为0.

if (root == null) return 0;

确定单层递归的逻辑
这块和求最大深度不一样，会写出如下代码：

int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
int result = 1 + Math.min(leftDepth, rightDepth);
return result;

这个代码就犯了此图中的误区：

如果这样求，没有左孩子的分支会算为最短深度。
所以，如果左子树为空，右子树不为空，说明最小速度为1 + 右子树的深度。
反之，异然。
最后如果左子树右子树都不为空，返回最小值+1；

代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int minDepth(TreeNode root) {if (root == null) return 0;if (root.left == null && root.right == null) {return 1;}int result = 0;int leftDepth = minDepth(root.left);int rightDepth = minDepth(root.right);if (root.left == null || root.right == null) return leftDepth + rightDepth + 1;result = Math.min(leftDepth, rightDepth) + 1;return result;}
}

思路二：广度优先搜索

本题还可以使用层序遍历的方法来解决，思路是一样的。
需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点。

代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int minDepth(TreeNode root) {if (root == null) {return 0;}Deque deque = new LinkedList<>();deque.offer(root);int depth = 0;while (!deque.isEmpty()) {int size = deque.size();depth++;for (int i = 0; i < size; i++) {TreeNode poll = deque.poll();if (poll.left == null && poll.right == null) {return depth;}if (poll.left != null) {deque.offer(poll.left);}if (poll.right != null) {deque.offer(poll.right);}}}return depth;}
}

二、二叉树的所有路径

思路一：递归法

我们使用前序遍历的方法！

确定递归终止条件
在写递归的时候我们习惯了这么写：

if (root == null) {终止处理逻辑
}

但是本题的终止条件这样写会很麻烦，因为本题要找到叶子节点，就开始结束的处理逻辑了（把路径放进result里）。

那么什么时候算是找到了叶子节点？ 是当 cur不为空，其左右孩子都为空的时候，就找到叶子节点。

if (root.left == null && root.right == null) {
}

为什么没有判断cur是否为空呢？因为下面的逻辑可以控制空节点不入循环。

我们使用List结构path来记录路径，所以要把List结构的path转为String格式，再把这个String放进result里。

为什么要是有List？因为在下面处理单层递归逻辑的时候，要做回溯，使用List方便回溯。

确定单层递归逻辑
因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路劲上的节点，先放进path中。
然后是递归和回溯的过程。上面说过没有判断root是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了。所以递归前要加上判断语句，下面要递归的节点是否为空。
递归完，要做回溯啊，因为path 不能一直加入节点，它还要删节点，然后才能加入新的节点。
回溯和递归是一一对应的，有一个递归，就要有一个回溯，这么写的话相当于把递归和回溯拆开了， 一个在花括号里，一个在花括号外。

所以回溯要和递归永远在一起，世界上最遥远的距离是你在花括号里，而我在花括号外！

代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List binaryTreePaths(TreeNode root) {List res = new ArrayList<>();if (root == null) {return res;}List paths = new ArrayList<>();traversal(root, paths, res);return res;}private void traversal(TreeNode root, List paths, List res) {paths.add(root.val);// 叶子结点if (root.left == null && root.right == null) {// 输出StringBuilder sb = new StringBuilder();for (int i = 0; i < paths.size() - 1; i++) {sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size() - 1));res.add(sb.toString());return;}if (root.left != null) {traversal(root.left, paths, res);paths.remove(paths.size() - 1);// 回溯}if (root.right != null) {traversal(root.right, paths, res);paths.remove(paths.size() - 1);// 回溯}}
}

思路二：迭代法

至于非递归的方式，我们可以依然可以使用前序遍历的迭代方式来模拟遍历路径的过程，这里除了模拟递归需要一个栈，同时还需要一个栈来存放对应的遍历路径。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List binaryTreePaths(TreeNode root) {List result = new ArrayList<>();if (root == null)return result;Stack