leetcode:111. 二叉树的最小深度

111. 二叉树的最小深度

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/minimum-depth-of-binary-tree

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

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

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

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

• 树中节点数的范围在 $[0,10^5]$ 内
• $-1000<=Node.val<=1000$

解法

• 递归：从根节点开始，如果该节点为空，则返回0；如果不为0，递归调用查找左右子树的深度，最终结果为根节点的1层+ min(left, right), 这里要注意，左右子节点一个为空的话，是需要继续往非空的节点往下走

  • 叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
  • 当 root 节点左右孩子都为空时，返回 1
  • 当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
  • 当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值

• bfs循环: bfs层序遍历，如果遍历到某个节点左右子节点都为空时候，即为该树的最小深度

代码实现

递归

python实现

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        if not root.left and not root.right:
            return 1
        
        if not root.left:
            return 1 + self.minDepth(root.right)
        
        if not root.right:
            return 1 + self.minDepth(root.left)
        
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

c++实现

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    int minDepth(TreeNode* root) {
     
        if (root == nullptr)
            return 0;
        if (root->left == nullptr && root->right == nullptr)
            return 1;
        if (root->left == nullptr)
            return 1 + minDepth(root->right);
        if (root->right == nullptr)
            return 1 + minDepth(root->left);

        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

复杂度分析

• 时间复杂度： $O(N)$ 每个节点都遍历一次
• 空间复杂度： $O(height)$ height是二叉树的高度，递归需要栈空间，栈空间取决于递归的深度

BFS循环

python实现

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        # bfs
        dq = []
        dq.append((1, root))
        while dq:
            depth, node = dq.pop(0)
            if not node.left and not node.right:
                return depth
            if node.left:
                dq.append([depth+1, node.left])
            if node.right:
                dq.append([depth+1, node.right])
        return depth

c++实现

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    int minDepth(TreeNode* root) {
    
        if (root == nullptr)
            return 0;
        
        int depth = 1;
        deque<pair<TreeNode*, int>> dq;
        dq.push_back({
    root, 1});

        while (dq.size() != 0) {
    
            TreeNode* node = dq.front().first;
            int depth = dq.front().second;

            dq.pop_front();
            if (node->left == nullptr && node->right == nullptr)
                return depth;
            
            if (node->left != nullptr)
                dq.push_back({
    node->left, depth+1});
            
            if (node->right != nullptr)
                dq.push_back({
    node->right, depth+1});
        }
        return depth;


    }
};

复杂度分析

• 时间复杂度： $O(N)$
• 空间复杂度： $O(N)$

参考

• c++ pair