1. Toy模板网首页
  2. > Toy博客

day16 二叉树的最大深度 n叉树的最大深度 二叉树的最小深度 完全二叉树的节点数

10月前 作者：人来茶热 分类：Toy博客 阅读(45) 违法举报

这篇具有很好参考价值的文章主要介绍了day16 二叉树的最大深度 n叉树的最大深度 二叉树的最小深度 完全二叉树的节点数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目1：104 二叉树的最大深度

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

题意

二叉树的根节点是root，返回其最大深度（从根节点到最远叶子节点的最长路径上的节点数）

递归

根节点的的高度就是二叉树的最大深度  所以使用后序遍历求最大高度的方式求出最大深度

递归三部曲

1）确定递归函数的参数和返回值

2）确定终止条件

3）确定单层递归的逻辑

day16 二叉树的最大深度 n叉树的最大深度 二叉树的最小深度 完全二叉树的节点数,算法,leetcode,动态规划

代码文章来源地址https://www.toymoban.com/news/detail-787540.html

/**
 * 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 result;
    int maxDepth(TreeNode* root) {
       //终止条件
       if(root==NULL) return 0;
       //单层递归逻辑  后序遍历 左右中
       int leftheight = maxDepth(root->left);//左
       int rightheight = maxDepth(root->right);//右
       int height = 1 + max(leftheight,rightheight);
       return height;
    }
};

层序遍历

最大深度就是判断二叉树有几层

代码

/**
 * 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 result;
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if(root!=NULL) que.push(root);
        int count = 0;
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            count++;
        }
        return count;   
    }
};
逻辑
例1：层次遍历只能使用队列不能使用栈，以下是使用栈的反例

day16 二叉树的最大深度 n叉树的最大深度 二叉树的最小深度 完全二叉树的节点数,算法,leetcode,动态规划

题目2：559 n叉树的最大深度

题目链接：555 n叉树的最大深度

题意

n叉树的最大深度

递归（难）

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        //终止条件
        if(root==NULL) return 0;
        //单层递归逻辑  后序遍历  左右中
        int depth = 0;
        for(int i=0;i<root->children.size();i++){
            depth = max(depth,maxDepth(root->children[i]));
            cout<<"node:"<<root->children[i]->val<<endl;;
            cout<<"depth:"<<depth<<endl;
        }
        return depth+1;
    }
};

层序遍历

一个node可能有多个孩子

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        queue<Node*> que;
        if(root!=NULL) que.push(root);
        int count = 0;
        while(!que.empty()){
            int size = que.size();
            while(size--){
                Node* node = que.front();
                que.pop();
                //一个node可能有多个海泽
                for(int i=0;i<node->children.size();i++){
                    if(node->children[i]) que.push(node->children[i]);
                }
            }
            count++;
        }
        return count;
    }
};

题目3：111 二叉树的最小深度

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

题意

根据二叉树的根节点root，找出其最小深度（根节点到最近叶子节点的路径上的节点数量）

递归

递归三部曲：

1）确定递归函数的返回值和参数

2）确定终止条件

3）确定单层递归逻辑

左子树为空，右子树不为空，最小深度是1+右子树的深度

左子树不为空，右子树为空，最小深度是1+左子树的深度

左子树不为空，右子树也不为空，最小深度是左右子树深度最小值+1

day16 二叉树的最大深度 n叉树的最大深度 二叉树的最小深度 完全二叉树的节点数,算法,leetcode,动态规划

代码

/**
 * 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==NULL) return 0;
       //单层递归逻辑  后序遍历  左右中
       int leftheight = minDepth(root->left);//左
       int rightheight = minDepth(root->right);//右
       //中
       if(root->left==NULL && root->right!=NULL) return 1 + rightheight;
       if(root->left!=NULL && root->right==NULL) return 1 + leftheight;
       int result = 1 + min(rightheight,leftheight);
       return result;
    }
};

层序遍历

遇到一个节点，该节点的左右孩子都为空，才是最终的叶子节点，return height即可

代码

/**
 * 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) {
       queue<TreeNode*> que;
       int count = 0;
       if(root!=NULL) que.push(root);
       while(!que.empty()){
           int size =que.size();
           count++;//这时count必须在前面,不能写在后面,要先加
           //如果写在后面，有可能还没有加呢,就直接满足node->left和node->right都为空就直接return了
           while(size--){
               TreeNode* node = que.front();
               que.pop();
               if(node->left){
                   que.push(node->left);
               }
               if(node->right){
                   que.push(node->right);
               }
               if(node->left==NULL && node->right==NULL){
                   return count;
               }   
           }
       }
       return count;  
    }
};

题目4：222 完全二叉树的节点个数

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

题意

根据完全二叉树的根节点root，求出该树的节点个数

递归

递归三部曲

1）确定递归函数的参数和返回值

2）确定终止条件

3）确定单层递归的逻辑

后序遍历
普通二叉树

day16 二叉树的最大深度 n叉树的最大深度 二叉树的最小深度 完全二叉树的节点数,算法,leetcode,动态规划

代码

/**
 * 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 countNodes(TreeNode* root) {
        //终止条件
        if(root==NULL) return 0;
        //单层递归逻辑 后序遍历 左右中
        int leftnum = countNodes(root->left);
        int rightnum = countNodes(root->right);
        int result = leftnum + rightnum + 1;
        return result;
    }
};
  • 时间复杂度：O(n)  遍历了所有节点
  • 空间复杂度：O(log n)，算上了递归系统栈占用的空间 
完全二叉树

day16 二叉树的最大深度 n叉树的最大深度 二叉树的最小深度 完全二叉树的节点数,算法,leetcode,动态规划

代码

/**
 * 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 countNodes(TreeNode* root) {
        //终止条件  空节点，子树为满二叉树
        if(root==NULL) return 0;//空节点
        TreeNode* leftnode = root->left;
        TreeNode* rightnode = root->right;
        int leftdepth = 0;
        int rightdepth = 0;
        while(leftnode){
            leftnode = leftnode->left;
            leftdepth++;
        }
        while(rightnode){
            rightnode = rightnode->right;
            rightdepth++;
        }
        if(leftdepth==rightdepth) return (2<<leftdepth)-1;//子树是满二叉树
        //单层递归逻辑
        int leftnum = countNodes(root->left);
        int rightnum = countNodes(root->right);
        int result = leftnum + rightnum + 1;
        return result;
    }
};
  • 时间复杂度：O(log n × log n)
  • 空间复杂度：O(log n)

层序遍历

可以求任意一个二叉树的节点个数，并没有用上题目中说的完全二叉树的条件

代码

/**
 * 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 countNodes(TreeNode* root) {
        queue<TreeNode*> que;
        if(root!=NULL) que.push(root);
        int count = 0;
        while(!que.empty()){
            int size = que.size();
            while(size--){
                count++;
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return count;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

到了这里，关于day16 二叉树的最大深度 n叉树的最大深度 二叉树的最小深度 完全二叉树的节点数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包