首页 > 其他分享 >代码随想录第15天,110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之和, 222.完全二叉树的节点个数

代码随想录第15天,110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之和, 222.完全二叉树的节点个数

时间:2024-08-24 17:22:08浏览次数:11  
标签:right TreeNode int 随想录 二叉树 new 15 root left

110.平衡二叉树

// 平衡二叉树,理解稍微有点难度
#include <iostream>
#include <algorithm> // For std::abs and std::max functions

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 辅助函数,计算二叉树的高度,并检查是否平衡
int getHeight(TreeNode *root)
{
    if (root == NULL)
        return 0;
    int leftHeight = getHeight(root->left);
    if (leftHeight == -1)
        return -1;
    int rightHeight = getHeight(root->right);
    if (rightHeight == -1)
        return -1;
    return abs(leftHeight - rightHeight) > 1 ? -1 : std::max(leftHeight, rightHeight) + 1;
}

// 主函数,判断二叉树是否平衡
bool isBalanced(TreeNode *root)
{
    return getHeight(root) == -1 ? false : true;
}

int main()
{
    // 构建一个简单的二叉树作为例子
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(3); // 添加深层左子树来制造不平衡
    root->right = new TreeNode(4);

    // 检查是否平衡
    bool result = isBalanced(root);
    std::cout << "Is the tree balanced? " << (result ? "Yes" : "No") << std::endl;

    return 0;
}

257. 二叉树的所有路径

#include <iostream>
#include <vector>
#include <string>

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 辅助函数,用于递归遍历并收集路径,注意传参当前路径也可以用引用,相当于添加了回溯过程
void dfs(TreeNode *node, std::vector<std::string> &paths, std::string currentPath)
{
    if (node == nullptr)
    {
        return; // 如果节点为空,直接返回
    }

    // 将当前节点值添加到路径中,注意要在叶子节点的前面
    currentPath += std::to_string(node->val);

    // 如果是叶子节点,将路径添加到结果集中
    if (node->left == nullptr && node->right == nullptr)
    {
        paths.push_back(currentPath);
    }
    else
    {
        // 如果不是叶子节点,继续递归遍历
        currentPath += "->"; // 使用箭头作为节点分隔符
        dfs(node->left, paths, currentPath);
        dfs(node->right, paths, currentPath);
    }
}

// 主函数,返回所有从根节点到叶子节点的路径
std::vector<std::string> binaryTreePaths(TreeNode *root)
{
    std::vector<std::string> paths;
    dfs(root, paths, "");
    return paths;
}

int main()
{
    // 构建一个简单的二叉树作为例子
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);

    // 收集所有路径
    std::vector<std::string> paths = binaryTreePaths(root);

    // 打印所有路径
    for (const std::string &path : paths)
    {
        std::cout << path << std::endl;
    }

    return 0;
}

404.左叶子之和

#include <iostream>

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 辅助函数,用于递归遍历并检测左叶子节点
int sumOfLeftLeaves(TreeNode *node, bool isLeft)
{
    if (node == nullptr)
    {
        return 0; // 如果节点为空,返回0
    }

    // 如果当前节点是叶子节点并且是左节点
    if (node->left == nullptr && node->right == nullptr && isLeft)
    {
        return node->val;
    }

    // 递归计算左子树和右子树的左叶子之和
    return sumOfLeftLeaves(node->left, true) + sumOfLeftLeaves(node->right, false);
}

// 另外一种写法在节点上一级操作更加简洁
int sumOfLeftLeaves2(TreeNode *root)
{
    if (root == NULL)
        return 0;
    int leftValue = 0;
    if (root->left != NULL && root->left->left == NULL && root->left->right == NULL)
    {
        leftValue = root->left->val;
    }
    return leftValue + sumOfLeftLeaves2(root->left) + sumOfLeftLeaves2(root->right);
}

// 主函数,返回所有左叶子之和
int sumOfLeftLeaves(TreeNode *root)
{
    return sumOfLeftLeaves2(root);
}

int main()
{
    // 构建一个简单的二叉树作为例子
    TreeNode *root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    // 计算所有左叶子节点之和
    std::cout << "Sum of all left leaves: " << sumOfLeftLeaves(root) << std::endl;

    return 0;
}

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

// 完全二叉树的节点个数
#include <iostream>

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 计算树的高度
int computeHeight(TreeNode *node)
{
    int height = 0;
    while (node != nullptr)
    {
        height++;
        node = node->left; // 移动到左子树
    }
    return height;
}

// 计算完全二叉树的节点总数
int countNodes(TreeNode *root)
{
    if (root == nullptr)
    {
        return 0;
    }

    int leftHeight = computeHeight(root->left);
    int rightHeight = computeHeight(root->right);

    if (leftHeight == rightHeight)
    {
        // 左子树是满的
        return (1 << leftHeight) + countNodes(root->right);
    }
    else
    {
        // 右子树是满的
        return (1 << rightHeight) + countNodes(root->left);
    }
}

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

    // 计算完全二叉树的节点总数
    std::cout << "Total number of nodes: " << countNodes(root) << std::endl;

    return 0;
}

标签:right,TreeNode,int,随想录,二叉树,new,15,root,left
From: https://blog.csdn.net/weixin_48850397/article/details/141395569

相关文章

  • 代码随想录第16天:513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造
    513.找树左下角的值,层序遍历//找树左下角的值,用层序遍历很容易实现#include<iostream>#include<queue>structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};//找到最底层......
  • 150页的极简大模型入门蛇尾书,学大模型太简单了
    如果问个问题:有哪些产品曾经创造了伟大的奇迹?ChatGPT应该会当之无愧入选。仅仅发布5天,ChatGPT就吸引了100万用户——当然,数据不是关键,关键是其背后的技术开启了新的AI狂潮,成为技术变革的点火器。就算我们这些周边吃瓜群众都日日活在ChatGPT带来的震撼里,更不用说在......
  • 二叉树的前序遍历(递归和非递归)
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(nullptr),right(nullptr){}*TreeNode(intx):val(x),left(nullptr),right(nullptr){}*......
  • LeetCode-Python-1650. 二叉树的最近公共祖先 III
    给定一棵二叉树中的两个节点 p 和 q,返回它们的最近公共祖先节点(LCA)。每个节点都包含其父节点的引用(指针)。Node 的定义如下:classNode{publicintval;publicNodeleft;publicNoderight;publicNodeparent;}根据维基百科中对最近公共祖先节点......
  • 【LeetCode面试150】——36有效的数独
    博客昵称:沈小农学编程作者简介:一名在读硕士,定期更新相关算法面试题,欢迎关注小弟!PS:哈喽!各位CSDN的uu们,我是你的小弟沈小农,希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正,觉得好的话别忘了一键三连哦!......
  • 【LeetCode面试150】——3无重复数组的最长子串
    博客昵称:沈小农学编程作者简介:一名在读硕士,定期更新相关算法面试题,欢迎关注小弟!PS:哈喽!各位CSDN的uu们,我是你的小弟沈小农,希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正,觉得好的话别忘了一键三连哦!......
  • 代码随想录day39 || 198 打家劫舍,213 打家劫舍||,337 打家劫舍|||
    198打家劫舍funcrob(nums[]int)int{ //思路,动态规划 //dp[i]代表前下标为i能装的最大盗窃物品价值 //递推dp[i]=max(dp[i-1],dp[i-2]+v(i))//dp[i-1]代表不偷物品i,dp[i-2]+v(i)代表偷物品i,那么就不能偷i-1,因为题目要求不能相邻,所以考虑前i-2 //dp[0]=0,......
  • 015java jsp SSM springboot在线视频课程教育学习平台系统(源码+文档+PPT+开题+运行视
     项目技术:Springboot+Maven+Vue等等组成,B/S模式+Maven管理等等。环境需要1.运行环境:最好是javajdk1.8,我们在这个平台上运行的。其他版本理论上也可以。2.IDE环境:IDEA,Eclipse,Myeclipse都可以。推荐IDEA;3.tomcat环境:Tomcat7.x,8.x,9.x版本均可4.硬件环境:window......
  • 「代码随想录算法训练营」第四十五天 | 图论 part3
    目录101.孤岛的总面积DFS思路BFS思路102.沉没孤岛103.水流问题104.建造最大岛屿101.孤岛的总面积题目链接:https://kamacoder.com/problempage.php?pid=1173文章讲解:https://programmercarl.com/kamacoder/0101.孤岛的总面积.html题目状态:看题解DFS思路思路:代码结构......
  • 「杂题乱刷2」CF1567D
    duel到的。题目链接CF1567D解题思路发现在越高的数位上,你获取的利益就会越大。因此你肯定是每次将尽可能多的数分到最高的数位上是最优的。但是你会发现,有可能你这样分数位后后面的数就分不到权值了,你只需要保证去掉当前分掉的权值之后,剩下可以分的权值不小于还剩下没分到......