easy 二叉树的最小深度 深度优先搜索 递归 广度优先搜索 队列 迭代

深度优先搜索 迭代：

不能碰到 null节点 就返回，null节点 的左右节点可能 非null

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 && root->right){  // 左右树都不为空
            return min(minDepth(root->left), minDepth(root->right)) + 1;
        }

        // 左右树有一个为空，返回不为空的树(max)深度+1
        // 左右树都为空(深度为0)，返回0+1
        return max(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

           

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 root.left and root.right:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        else:
            return max(self.minDepth(root.left), self.minDepth(root.right)) + 1

           

广度优先搜索 队列 迭代：

层序遍历

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;
        }
        queue<TreeNode*> que;
        que.push(root);
        int d = 0;
        while(!que.empty()){
            d++;  // root 不为空，层数+1
            int n = que.size();  //  记录每一层元素个数
            while(n){
                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 d;
                }
                n--;  // 该层元素-1
            }
        }

        return d;
    }
};

           

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

        q = collections.deque([root])   # 创建python双端队列，并放入p
        h = 0
        while q:

            h +=1
            n = len(q)  # 这一层中元素的个数
            while n:
                node = q.popleft()  # 返回并删除队列顶端元素
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                if not node.left and not node.right:
                    return h

                n -= 1 # 这一层中元素的个数-1

            # h +=1  # 不能在此处才处理h

        return h