代码随想录算法训练营第十六天 | 104.二叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数

104.二叉树的最大深度

题目链接：104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

文章讲解/视频讲解：https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html

思路

可以采用递归和迭代两种方法实现。

递归：求得当前节点左右孩子的深度depth1和depth2，取二者最大值+1，便为当前节点到叶子节点的最大长度。从根节点递归求解这一过程，便可得出二叉树的最大深度。

迭代：用层序遍历来解决，使用depth变量记录当前节点深度，每一层遍历将depth+1，一直到遍历结束，便可得到最大深度值。

C++实现

// 递归法
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int maxDepth1 = maxDepth(root->left);
        int maxDepth2 = maxDepth(root->right);
        return max(maxDepth1, maxDepth2) + 1;    
    }
};

// 迭代法
class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        int depth = 0;
        if(root != nullptr) que.push(root);
        while(!que.empty()){
            int qSize = que.size();
            depth += 1;
            for(int i = 0;i<qSize;i++){
                TreeNode* cur = que.front();
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return depth;
    }
};

111.二叉树的最小深度

题目链接：111. 二叉树的最小深度

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

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

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

文章讲解/视频讲解：https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html

思路

与上一题类似，也可采用递归或迭代法来解决。

递归：使用一个min_depth变量记录二叉树的全局最小深度，然后递归搜寻二叉树，记录每个叶子节点的深度，将最小的深度赋予min_depth。

迭代：采用层序遍历，如果在遍历时，第一次发现当前有一个节点既没有左子树又没有右子树，则当前节点的深度为二叉树的最小深度。

C++实现

// 递归法
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int min_depth = numeric_limits<int>::max();
        dfs(root, 1, min_depth);
        return min_depth;
    }

    void dfs(TreeNode* node, int cur_depth, int& min_depth){
        if(node == nullptr) return;
        if(node->left == nullptr && node->right == nullptr){
            min_depth = min(min_depth, cur_depth);
        }
        if(node->left) dfs(node->left, cur_depth + 1, min_depth);
        if(node->right) dfs(node->right, cur_depth + 1, min_depth);
    }
};
// 迭代法
class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> queue;
        int minDepth = 0;
        if(root != nullptr) queue.push(root);
        bool foundLeaf = false;
        while(!queue.empty()){
            int qSize = queue.size();
            minDepth += 1;
            for(int i = 0;i<qSize;i++){
                TreeNode* cur = queue.front();
                queue.pop();
                bool isLeaf = !cur->left && !cur->right;
                if(isLeaf){
                    foundLeaf = true;
                    break;
                }

                if(cur->left) queue.push(cur->left);
                if(cur->right) queue.push(cur->right);
            }
            if(foundLeaf) break;
        }
        return minDepth;
    }
};

222.完全二叉树的节点个数

题目链接：完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

文章讲解/视频讲解：https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html

思路

有递归和迭代两种思路。

递归：用深度优先遍历的方式把整个二叉树遍历一遍，每一次遍历将个数加一。

迭代：用层序遍历的方式把整个二叉树过一遍，每遍历一个节点将节点个数加一。

C++实现

// 递归法
class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> que;
        int count = 0;
        if(root != nullptr) que.push(root);

        while(!que.empty()){
            TreeNode* cur = que.front();
            que.pop();
            count++;
            if(cur->left != nullptr) que.push(cur->left);
            if(cur->right != nullptr) que.push(cur->right);
        }
        return count;
    }
};

// 迭代法
class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> que;
        int count = 0;
        if(root != nullptr) que.push(root);

        while(!que.empty()){
            TreeNode* cur = que.front();
            que.pop();
            count++;
            if(cur->left != nullptr) que.push(cur->left);
            if(cur->right != nullptr) que.push(cur->right);
        }
        return count;
    }
};