# 二叉树的最小深度问题

CSDN：二叉树的最小深度问题

## 二叉树的递归套路解法

``````int minDepth(TreeNode head)
``````

``````if (null == head) {
return 0;
}
``````

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

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

## 更多

原文作者：Grey Zeng
原文地址: https://www.cnblogs.com/greyzeng/p/16963808.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。