# 二叉树的最小深度(Minimum depth of binary tree)-其他

## 二叉树的最小深度(Minimum depth of binary tree)

### 二叉树的最小深度

《程序员代码面试指南》第33题 P100 难度：原问题 士★☆☆☆ 进阶问题 将★★★★

DFS（时间复杂度O(N)，空间复杂度O(H)）：

``````class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}

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

int min_depth = Integer.MAX_VALUE;
if (root.left != null) {
min_depth = Math.min(minDepth(root.left), min_depth);
}
if (root.right != null) {
min_depth = Math.min(minDepth(root.right), min_depth);
}

return min_depth + 1;
}
}

BFS（时间复杂度O(N)，空间复杂度O(N)）：

``````class Solution {
class QueueNode {
TreeNode node;
int depth;

public QueueNode(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}

public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}

queue.offer(new QueueNode(root, 1));
while (!queue.isEmpty()) {
QueueNode nodeDepth = queue.poll();
TreeNode node = nodeDepth.node;
int depth = nodeDepth.depth;
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.offer(new QueueNode(node.left, depth + 1));
}
if (node.right != null) {
queue.offer(new QueueNode(node.right, depth + 1));
}
}

return 0;
}
}

————————

### Minimum depth of binary tree

Title: minimum depth of binary tree

“Programmer code interview guide” question 33 P100 difficulty: original question ★☆☆☆ advanced question ★★★★

There are ordinary solutions and advanced solutions in this problem book. The advanced solution uses the divine method of traversing the binary tree – Morris traversal. Don’t look at it for the time being and come back to make up when you have time.

The general solution is introduced below. It is very simple to find all leaf nodes < / strong > during < strong > traversal, and know the height of the < strong > leaf node < / strong >. Finally, find the < strong > minimum value of all leaf node heights < / strong >.

Niuke doesn’t have this question. There are two methods on the force button: < strong > depth first search < / strong > and < strong > breadth first search < / strong >.

< strong > DFS < / strong > (time complexity O (n), space complexity O (H)):

``````class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}

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

int min_depth = Integer.MAX_VALUE;
if (root.left != null) {
min_depth = Math.min(minDepth(root.left), min_depth);
}
if (root.right != null) {
min_depth = Math.min(minDepth(root.right), min_depth);
}

return min_depth + 1;
}
}

It is not difficult to find that after recursion < strong > until the leaf node < / strong > is found, < strong > returns the depth of 1 < / strong >, then < strong > adds 1 < / strong > layer by layer from bottom to top, and < strong > each time the left and right subtrees take the minimum depth < / strong >. Go to the first layer < strong > root node < / strong >, similarly, find the minimum depth of the left and right subtrees, and then < strong > return the depth plus 1 < / strong >, that is, add the depth of the root node, which is < strong > the minimum depth of the whole binary tree < / strong >.

< strong > BFS < / strong > (time complexity O (n), space complexity O (n)):

``````class Solution {
class QueueNode {
TreeNode node;
int depth;

public QueueNode(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}

public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}

queue.offer(new QueueNode(root, 1));
while (!queue.isEmpty()) {
QueueNode nodeDepth = queue.poll();
TreeNode node = nodeDepth.node;
int depth = nodeDepth.depth;
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.offer(new QueueNode(node.left, depth + 1));
}
if (node.right != null) {
queue.offer(new QueueNode(node.right, depth + 1));
}
}

return 0;
}
}

It can be seen that the data structure of < strong > queue < / strong > is used. Each time < strong > takes out a node < / strong > from the head of the queue, its < strong > left subtree and right subtree < / strong > (if any) are placed in the tail of the queue < / strong >, forming the process of < strong > sequence history < / strong >.

Special instructions for < strong > breadth first search < / strong >:

When < strong > finds a leaf node < / strong >, < strong > directly returns the depth of the leaf node < / strong >. The breadth first search ensures that the depth of the first leaf node to be searched must be the smallest < / strong >.

This is because breadth first search is equivalent to < strong > sequence traversal < / strong > binary tree. If < strong > a node is a leaf node < / strong >, it means that < strong > there has been no leaf node < / strong > (otherwise it has been returned) in the current layer and all previous layers. Therefore, < strong > the depth of the first searched leaf node must be the smallest < / strong >.