参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

和求最大深度一个套路？

111.二叉树的最小深度

力扣题目链接

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

返回它的最小深度 2.

思路

看完了这篇104.二叉树的最大深度，再来看看如何求最小深度。

直觉上好像和求最大深度差不多，其实还是差不少的。

本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）

那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，这不过这个最小距离也同样是最小深度。

以下讲解中遍历顺序上依然采用后序遍历（因为要比较递归返回之后的结果，本文我也给出前序遍历的写法）。

本题还有一个误区，在处理节点的过程中，最大深度很容易理解，最小深度就不那么好理解，如图：

这就重新审题了，题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。

什么是叶子节点，左右孩子都为空的节点才是叶子节点！

递归法

来来来，一起递归三部曲：

确定递归函数的参数和返回值

参数为要传入的二叉树根节点，返回的是int类型的深度。

代码如下：

int getDepth(TreeNode* node)

确定终止条件

终止条件也是遇到空节点返回0，表示当前节点的高度为0。

代码如下：

if (node == NULL) return 0;

确定单层递归的逻辑

这块和求最大深度可就不一样了，一些同学可能会写如下代码：

int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);
return result;

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

如果这么求的话，没有左孩子的分支会算为最短深度。

所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。

反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

代码如下：

int leftDepth = getDepth(node->left);           // 左
int rightDepth = getDepth(node->right);         // 右
                                                // 中
// 当一个左子树为空，右不为空，这时并不是最低点
if (node->left == NULL && node->right != NULL) { 
    return 1 + rightDepth;
}   
// 当一个右子树为空，左不为空，这时并不是最低点
if (node->left != NULL && node->right == NULL) { 
    return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;

遍历的顺序为后序（左右中），可以看出：求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

整体递归代码如下：

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

精简之后代码如下：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right != NULL) {
            return 1 + minDepth(root->right);
        }
        if (root->left != NULL && root->right == NULL) {
            return 1 + minDepth(root->left);
        }
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

精简之后的代码根本看不出是哪种遍历方式，所以依然还要强调一波：如果对二叉树的操作还不熟练，尽量不要直接照着精简代码来学。

前序遍历的方式：

class Solution {
private:
    int result;
    void getdepth(TreeNode* node, int depth) {
        if (node->left == NULL && node->right == NULL) {
            result = min(depth, result);  
            return;
        }
        // 中 只不过中没有处理的逻辑
        if (node->left) { // 左
            getdepth(node->left, depth + 1);
        }
        if (node->right) { // 右
            getdepth(node->right, depth + 1);
        }
        return ;
    }

public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        result = INT_MAX;
        getdepth(root, 1);
        return result;
    }
};

迭代法

相对于104.二叉树的最大深度，本题还可以使用层序遍历的方式来解决，思路是一样的。

如果对层序遍历还不清楚的话，可以看这篇：二叉树：层序遍历登场！

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

代码如下：（详细注释）

class Solution {
public:

    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录最小深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    return depth;
                }
            }
        }
        return depth;
    }
};

其他语言版本

Java

class Solution {
    /**
     * 递归法，相比求MaxDepth要复杂点
     * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        // 左右结点都不为null
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

class Solution {
   /**
     * 迭代法，层序遍历
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> 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) {
                    // 是叶子结点，直接返回depth，因为从上往下遍历，所以该值就是最小值
                    return depth;
                }
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
    }
}

Python

递归法：

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1

        min_depth = 10**9
        if root.left:
            min_depth = min(self.minDepth(root.left), min_depth) # 获得左子树的最小高度
        if root.right:
            min_depth = min(self.minDepth(root.right), min_depth) # 获得右子树的最小高度
        return min_depth + 1

迭代法：

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        que = deque()
        que.append(root)
        res = 1

        while que:
            for _ in range(len(que)):
                node = que.popleft()
                # 当左右孩子都为空的时候，说明是最低点的一层了，退出
                if not node.left and not node.right:
                    return res
                if node.left is not None:
                    que.append(node.left)
                if node.right is not None:
                    que.append(node.right)
            res += 1
        return res

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func min(a, b int) int {
    if a < b {
        return a;
    }
    return b;
}
// 递归
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0;
    }
    if root.Left == nil && root.Right != nil {
        return 1 + minDepth(root.Right);
    }
    if root.Right == nil && root.Left != nil {
        return 1 + minDepth(root.Left);
    }
    return min(minDepth(root.Left), minDepth(root.Right)) + 1;
}

// 迭代

func minDepth(root *TreeNode) int {
    dep := 0;
    queue := make([]*TreeNode, 0);
    if root != nil {
        queue = append(queue, root);
    }
    for l := len(queue); l > 0; {
        dep++;
        for ; l > 0; l-- {
            node := queue[0];
            if node.Left == nil && node.Right == nil {
                return dep;
            }
            if node.Left != nil {
                queue = append(queue, node.Left);
            }
            if node.Right != nil {
                queue = append(queue, node.Right);
            }
            queue = queue[1:];
        }
        l = len(queue);
    } 
    return dep;
}

JavaScript

递归法：

/**
    * @param {TreeNode} root
    * @return {number}
    */
var minDepth1 = function(root) {
    if(!root) return 0;
    // 到叶子节点 返回 1
    if(!root.left && !root.right) return 1;
    // 只有右节点时 递归右节点
    if(!root.left) return 1 + minDepth(root.right);
    // 只有左节点时 递归左节点
    if(!root.right) return 1 + minDepth(root.left);
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

迭代法：

/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
    if(!root) return 0;
    const queue = [root];
    let dep = 0;
    while(true) {
        let size = queue.length;
        dep++;
        while(size--){
            const node = queue.shift();
            // 到第一个叶子节点 返回 当前深度 
            if(!node.left && !node.right) return dep;
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
};

TypeScript

递归法

function minDepth(root: TreeNode | null): number {
    if (root === null) return 0;
    if (root.left !== null && root.right === null) {
        return 1 + minDepth(root.left);
    }
    if (root.left === null && root.right !== null) {
        return 1 + minDepth(root.right);
    }
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

迭代法

function minDepth(root: TreeNode | null): number {
    let helperQueue: TreeNode[] = [];
    let resMin: number = 0;
    let tempNode: TreeNode;
    if (root !== null) helperQueue.push(root);
    while (helperQueue.length > 0) {
        resMin++;
        for (let i = 0, length = helperQueue.length; i < length; i++) {
            tempNode = helperQueue.shift()!;
            if (tempNode.left === null && tempNode.right === null) return resMin;
            if (tempNode.left !== null) helperQueue.push(tempNode.left);
            if (tempNode.right !== null) helperQueue.push(tempNode.right);
        }
    }
    return resMin;
};

Swift

递归

func minDepth(_ root: TreeNode?) -> Int {
    guard let root = root else {
        return 0
    }
    if root.left == nil && root.right != nil {
        return 1 + minDepth(root.right)
    }
    if root.left != nil && root.right == nil {
        return 1 + minDepth(root.left)
    }
    return 1 + min(minDepth(root.left), minDepth(root.right))
}

迭代

func minDepth(_ root: TreeNode?) -> Int {
    guard let root = root else {
        return 0
    }
    var res = 0
    var queue = [TreeNode]()
    queue.append(root)
    while !queue.isEmpty {
        res += 1
        for _ in 0 ..< queue.count {
            let node = queue.removeFirst()
            if node.left == nil && node.right == nil {
                return res
            }
            if let left = node.left {
                queue.append(left)
            }
            if let right = node.right {
                queue.append(right)
            }
        }
    }
    return res
}

Scala

递归法:

object Solution {
  def minDepth(root: TreeNode): Int = {
    if (root == null) return 0
    if (root.left == null && root.right != null) return 1 + minDepth(root.right)
    if (root.left != null && root.right == null) return 1 + minDepth(root.left)
    // 如果两侧都不为空，则取最小值，return关键字可以省略
    1 + math.min(minDepth(root.left), minDepth(root.right))
  }
}

迭代法:

object Solution {
  import scala.collection.mutable
  def minDepth(root: TreeNode): Int = {
    if (root == null) return 0
    var depth = 0
    val queue = mutable.Queue[TreeNode]()
    queue.enqueue(root)
    while (!queue.isEmpty) {
      depth += 1
      val len = queue.size
      for (i <- 0 until len) {
        val curNode = queue.dequeue()
        if (curNode.left != null) queue.enqueue(curNode.left)
        if (curNode.right != null) queue.enqueue(curNode.right)
        if (curNode.left == null && curNode.right == null) return depth
      }
    }
    depth
  }
}

rust:

impl Solution {
    pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        return Solution::bfs(root)
    }

    // 递归
    pub fn dfs(node: Option<Rc<RefCell<TreeNode>>>) -> i32{
        if node.is_none(){
            return 0;
        }
        let parent = node.unwrap();
        let left_child = parent.borrow_mut().left.take();
        let right_child = parent.borrow_mut().right.take();
        if left_child.is_none() && right_child.is_none(){
            return 1;
        }
        let mut min_depth = i32::MAX;
        if left_child.is_some(){
            let left_depth = Solution::dfs(left_child);
            if left_depth <= min_depth{
                min_depth = left_depth
            }
        }
        if right_child.is_some(){
            let right_depth = Solution::dfs(right_child);
            if right_depth <= min_depth{
                min_depth = right_depth
            }
        }
        min_depth + 1

    }

    // 迭代
    pub fn bfs(node: Option<Rc<RefCell<TreeNode>>>) -> i32{
        let mut min_depth = 0;
        if node.is_none(){
            return min_depth
        }
        let mut stack = vec![node.unwrap()];
        while !stack.is_empty(){
            min_depth += 1;
            let num = stack.len();
            for _i in 0..num{
                let top = stack.remove(0);
                let left_child = top.borrow_mut().left.take();
                let right_child = top.borrow_mut().right.take();
                if left_child.is_none() && right_child.is_none(){
                    return min_depth;
                }
                if left_child.is_some(){
                    stack.push(left_child.unwrap());
                }
                if right_child.is_some(){
                    stack.push(right_child.unwrap());
                }
            }
        }
        min_depth
    }

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0111.二叉树的最小深度.md

0111.二叉树的最小深度.md

111.二叉树的最小深度

思路

递归法

迭代法

其他语言版本

Java

Python

Go

JavaScript

TypeScript

Swift

Scala

Files

0111.二叉树的最小深度.md

Latest commit

History

0111.二叉树的最小深度.md

File metadata and controls

111.二叉树的最小深度

思路

递归法

迭代法

其他语言版本

Java

Python

Go

JavaScript

TypeScript

Swift

Scala