二叉树的最小深度问题
作者：Grey
原文地址：
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
题目链接见：LeetCode 111. Minimum Depth of Binary Tree
本题可以用两种方法来解，第一种方法，使用二叉树的递归套路，第二种方法是 Morris 遍历。
二叉树的递归套路解法
相关介绍见:使用二叉树的递归套路来解决的问题
定义递归函数
int minDepth(TreeNode head)
递归含义表示：以 head 为头的二叉树的最小深度为多少。
接下来是 base case，
if (null == head) {
return 0;
}
显而易见，空树的深度是0；
接下来是普遍情况：
如果 head 的左树为空，则最小深度就是右树的最小深度加1；
如果 head 的右树为空，则最小深度就是左树的最小深度加1；
如果 head 的左右树都不为空，则最小深度就是左右树深度更大的那个加1。
完整代码如下
public static int minDepth(TreeNode head) {
if (head == null) {
return 0;
}
if (head.left == null) {
return minDepth(head.right) + 1;
}
if (head.right == null) {
return minDepth(head.left) + 1;
}
return Math.min(minDepth(head.left), minDepth(head.right)) + 1;
}
这个解法的时间复杂度是O(N)；
如果递归栈算空间的话，整个算法空间复杂度就是递归栈的复杂度O(N)。
Morris 遍历解法
使用 Morris 遍历，可以实现空间复杂度达到O(1),时间复杂度保持O(N)，Morris算法的介绍见:Morris 遍历实现二叉树的遍历
本题如果要用Morris遍历，需要解决的第一个问题是Morris发现当前层？
即：假设上一个节点是 X，在第 8 层，下一个遍历的节点是 Y，如何判断 Y 在第几层？
结论是：如果Y左树的最右节点是 A（非 X ），Y 必定是第 9 层，如果 Y 左树的最右节点是 X，那 Y 在第 X 层数-Y 的左树的右节点的个数
需要解决的第二个问题是Morris发现叶节点？
结论是：每个结点第二次回到自己的时候，因为要恢复指针，在恢复后，看下是否是叶子节点, 最后要单独遍历一下左树的最右节点。
完整代码见
public static int minDepth(TreeNode head) {
if (head == null) {
return 0;
}
TreeNode cur = head;
TreeNode mostRight;
int curHeight = 0;
int min = Integer.MAX_VALUE;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
int duplicate = 1;
while (mostRight.right != null && mostRight.right != cur) {
duplicate++;
mostRight = mostRight.right;
}
if (mostRight.right == null) {
curHeight++;
mostRight.right = cur;
cur = cur.left;
continue;
} else {
if (mostRight.left == null) {
min = Math.min(min, curHeight);
}
curHeight -= duplicate;
mostRight.right = null;
}
} else {
curHeight++;
}
cur = cur.right;
}
int rightMostHeight = 1;
TreeNode c = head;
while (c.right != null) {
rightMostHeight++;
c = c.right;
}
if (c.left == null) {
min = Math.min(min, rightMostHeight);
}
return min;
}