111.二叉树的最小深度 (Easy)*

题目描述*

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

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

示例*

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

返回它的最小深度 2.

代码*

递归，不过此时不能直接取两侧最小的深度，应该时当左右都不空时取最小，任一为空取非空的深度。之前也用 bfs 来找最大深度，现在可以改为到叶子节点就返回。

递归bfs

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

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        queue<TreeNode*> helpQueue;
        TreeNode *cur = root;
        helpQueue.push(cur);
        int depth = 1;
        while(!helpQueue.empty()) {
            int len = helpQueue.size();
            for(int i = 0; i < len; i++) {
                cur = helpQueue.front();
                helpQueue.pop();
                // 如果是叶子节点，就返回当前深度
                if(cur->left == nullptr && cur->right == nullptr) {
                    return depth;
                }
                if(cur->left != nullptr) {
                    helpQueue.push(cur->left);
                }
                if(cur->right != nullptr) {
                    helpQueue.push(cur->right);
                }

            }
            depth++;
        }
        return depth;
    }
};

最后更新: July 23, 2022