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

2023-12-28 13:49:58

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;
    }
};

文章来源:https://blog.csdn.net/weixin_43347688/article/details/135265879
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。