算法训练day16Leetcode104二叉树最大深度111二叉树最小深度222完全二叉树的节点个数

发布时间:2024年01月16日

今日学习的文章和视频链接

https://www.bilibili.com/video/BV1Gd4y1V75u/?vd_source=8272bd48fee17396a4a1746c256ab0ae

104 二叉树的最大深度

题目描述

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

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


 

输入:root = [3,9,20,null,null,15,7]
输出:3
示例 2:

输入:root = [1,null,2]
输出:2
 

提示:

树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100

我的思路

用递归,但是什么顺序没想清楚

题目分析

二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)

二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数或者节点数(取决于高度从0开始还是从1开始)

而根节点的高度就是二叉树的最大深度,所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

先用后序遍历(左右中)来计算树的高度。

确定递归函数的参数和返回值:参数就是传入树的根节点,返回就返回这棵树的深度,所以返回值为int类型。
代码如下:

int getdepth(TreeNode* node)

确定终止条件:如果为空节点的话,就返回0,表示高度为0。
代码如下:

if (node == NULL) return 0;

确定单层递归的逻辑:先求它的左子树的深度,再求右子树的深度,最后取左右深度最大的数值 再+1 (加1是因为算上当前中间节点)就是目前节点为根节点的树的深度。
代码如下:

int leftdepth = getdepth(node->left);       // 左
int rightdepth = getdepth(node->right);     // 右
int depth = 1 + max(leftdepth, rightdepth); // 中
return depth;

acm模式代码

int main() {
    // 创建二叉树的节点
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // 创建Solution实例
    Solution solution;

    // 计算并打印最大深度
    std::cout << "Maximum depth of the binary tree is: " << solution.maxDepth(root) << std::endl;

    // TODO: 释放分配的内存(在实际应用中很重要)
    // ...

    return 0;
}

111二叉树最小深度

题目描述

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

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

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

 

示例 1:


输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
 

提示:

树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000

我的想法

直接和上题一样,返回min+1

题目分析

本题依然是前序遍历和后序遍历都可以,前序求的是深度,后序求的是高度。

二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)

二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数后者节点数(取决于高度从0开始还是从1开始)

那么使用后序遍历,其实求的是根节点到叶子节点的最小距离,就是求高度的过程,不过这个最小距离 也同样是最小深度。

题目中说的是:最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。

什么是叶子节点,左右孩子都为空的节点才是叶子节点!

递归法:

递归三部曲:

确定递归函数的参数和返回值
参数为要传入的二叉树根节点,返回的是int类型的深度。

代码如下:

int getDepth(TreeNode* node)

确定终止条件
终止条件也是遇到空节点返回0,表示当前节点的高度为0。

代码如下:

if (node == NULL) return 0;

确定单层递归的逻辑
这块和求最大深度可就不一样了,一些同学可能会写如下代码:

int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);
return result;

如果这么求的话,没有左孩子的分支会算为最短深度。

所以,如果左子树为空,右子树不为空,说明最小深度是 1 + 右子树的深度。

反之,右子树为空,左子树不为空,最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空,返回左右子树深度最小值 + 1 。

acm模式代码

#include <iostream>
#include <algorithm>

struct  TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    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 getdepth (TreeNode* node) {
        if (node == nullptr) return 0;
        int leftdepth = getdepth(node->left);
        int rightdepth = getdepth(node->right);
        if (node->left == nullptr && node->right != nullptr) {
            return 1 + rightdepth;
        }
        if (node->left != nullptr && node->left == nullptr) {
            return 1 + leftdepth;
        }
        int depth = 1 + std::min(leftdepth, rightdepth);
        return depth;
    }
    int minDepth(TreeNode* root) {
        return getdepth(root);
    }
};

int main() {
    // 创建二叉树的节点
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    // root->left->right = new TreeNode(5);

    // 创建Solution实例
    Solution solution;

    // 计算并打印最小深度
    std::cout << "Minimum depth of the binary tree is: " << solution.minDepth(root) << std::endl;

    // TODO: 释放分配的内存(在实际应用中很重要)
    // ...

    return 0;
}

222完全二叉树的节点个数

题目描述

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

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

 

示例 1:


输入:root = [1,2,3,4,5,6]
输出:6
示例 2:

输入:root = []
输出:0
示例 3:

输入:root = [1]
输出:1
 

提示:

树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树
 

进阶:遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗?

我的想法

后序遍历统计节点个数

题目分析

普通二叉树可以求解,时间复杂度为n

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

可以看出如果整个树不是满二叉树,就递归其左右孩子,直到遇到满二叉树为止,用公式计算这个子树(满二叉树)的节点数量。

在完全二叉树中,如果递归向左遍历的深度等于递归向右遍历的深度,那说明就是满二叉树

acm模式代码

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    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 == nullptr) {
            return 0;
        }
        int countleft = 0;
        int countright=  0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        while(left) {
            left = left->left;
            countleft ++;
        }
        while (right) {
            right = right->right;
            countright ++;
        }
        if (countleft == countright) {
            return (2 << countleft) - 1;
        }


        int leftnodes = countNodes(root->left);
        int rightnodes=  countNodes(root->right);
        int sum = leftnodes + rightnodes + 1;
        return sum; 
    }
};

int main() {
    // 创建二叉树的节点
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    // 创建Solution实例
    Solution solution;

    // 计算并打印节点总数
    std::cout << "Total number of nodes in the binary tree is: " << solution.countNodes(root) << std::endl;

    // TODO: 释放分配的内存(在实际应用中很重要)
    // ...

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