首页 > 编程语言 >代码随想录算法训练营第十五天| 110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之和, 222.完全二叉树的节点个数

代码随想录算法训练营第十五天| 110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之和, 222.完全二叉树的节点个数

时间:2024-11-08 16:42:55浏览次数:1  
标签:return root 随想录 二叉树 https NULL 第十五天 left

110.平衡二叉树

文章链接:https://programmercarl.com/0110.平衡二叉树.html#题外话
题目链接:https://leetcode.cn/problems/balanced-binary-tree/description/

class Solution {
public:
    //每次都要比较左右子树的高度差是否在1以内,所以递归是要统计子树的高度的
    int getHeight(TreeNode* root){
        if(root==NULL) return 0;
        //获得左子树的高度,如果左子树高度为-1,说明已经失败了
        int leftHeight=getHeight(root->left);
        if(leftHeight==-1) return -1;
        //获得右子树的高度,如果右子树高度为-1,说明已经失败了
        int rightHeight=getHeight(root->right);
        if(rightHeight==-1) return -1;
        //如果左右子树的高度都不为-1,说明可以进行高度差的比较,判断是否在1以内
        if(abs(leftHeight-rightHeight)>1) return -1;
        //如果以上失败条件都能排除,则可以返回父节点的高度
        return 1+max(leftHeight,rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        if(getHeight(root)==-1) return false;
        return true;
    }
};

257. 二叉树的所有路径

文章链接:https://programmercarl.com/0257.二叉树的所有路径.html
题目链接:https://leetcode.cn/problems/binary-tree-paths/description/

class Solution {
    void traversal(TreeNode* node,string path,vector<string>&result){
        //这里一开始要加上叶子节点
        path+=to_string(node->val);
        //再处理叶子节点的情况
        if(node->right==NULL&&node->left==NULL){
            result.push_back(path);
            return;
        }
        //左
        if(node->left) traversal(node->left,path+"->",result);
        //右
        if(node->right) traversal(node->right,path+"->",result);
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if(root==NULL) return {};
        traversal(root,path,result);
        return result;
    }
};

404.左叶子之和

文章链接:https://programmercarl.com/0404.左叶子之和.html
题目链接:https://leetcode.cn/problems/sum-of-left-leaves/description/

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==NULL) return 0;
        int leftNum=0;
        //不断向下遍历,直到遇到符合条件的(左孩子为叶子节点)左叶子节点和的值才会增加
        if(root->left!=NULL&&root->left->left==NULL&&root->left->right==NULL){
            leftNum+=root->left->val;
        }
        return leftNum+sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
    }
};

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

文章链接:https://programmercarl.com/0222.完全二叉树的节点个数.html
题目链接:https://leetcode.cn/problems/count-complete-tree-nodes/

总结:直接做一个遍历即可

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==NULL) return 0;
        return 1+countNodes(root->left)+countNodes(root->right);
    }
};

标签:return,root,随想录,二叉树,https,NULL,第十五天,left
From: https://www.cnblogs.com/VickyWu/p/18531186

相关文章

  • 二叉树遍历
    二叉树遍历这个问题,以前一直没搞懂,只是模糊的了解。先序遍历:先访问根节点,再从左到右依次访问各子树。ABDECFG中序遍历:先访问左节点,再访问根节点,最后再访问右节点。DBEACGF后序遍历:先从左到右遍历各棵子树,再访问根节点。DEBGFCA先中后实际上对应的是根遍历的位置。层次遍历......
  • 代码随想录 -- 动态规划 -- 分割等和子集
    416.分割等和子集-力扣(LeetCode)思路:题目中表述:将数组nums分割成两个子集,使得两个子集的元素和相等。可以转化为:有一个背包,如果存在部分元素组合可以令容量为nums的和的一半的背包容纳的最大价值也为nums的和的一半,那么剩下的元素和也是nums的一半,则符合题意。dp[j]含义:......
  • 代码随想录算法训练营第二十一天| leetcode669. 修剪二叉搜索树、leetcode108.将有序
    1leetcode669.修剪二叉搜索树题目链接:669.修剪二叉搜索树-力扣(LeetCode)文章链接:代码随想录视频链接:你修剪的方式不对,我来给你纠正一下!|LeetCode:669.修剪二叉搜索树_哔哩哔哩_bilibili思路:目前想的是分三种情况,第一种情况就是这个数删除左边全部,第二种删除右边的全部,第......
  • 二叉树 (王道数据结构 C语言版)
    2004.11.04计算一颗给定二叉树的所有双分支节点个数编写把一个树的所有左右子树进行交换的函数求先序遍历中第k个结点的值(1<=k<=二叉树中的结点个数)#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;typedefstructBitnode{......
  • 代码随想录算法训练营第三十九天|Day39 动态规划
    198.打家劫舍视频讲解:https://www.bilibili.com/video/BV1Te411N7SXhttps://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html思路#definemax(a,b)((a)>(b)?(a):(b))introb(int*nums,intnumsSize){if(numsSize==0){re......
  • 代码随想录算法训练营第四十天|Day40 动态规划
    121.买卖股票的最佳时机视频讲解:https://www.bilibili.com/video/BV1Xe4y1u77qhttps://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html思路#definemax(a,b)((a)>(b)?(a):(b))#definemin......
  • 代码随想录算法训练营第二十天|leetcode235. 二叉搜索树的最近公共祖先、leetcode701.
    1leetcode235.二叉搜索树的最近公共祖先题目链接:235.二叉搜索树的最近公共祖先-力扣(LeetCode)文章链接:代码随想录视频链接:二叉搜索树找祖先就有点不一样了!|235.二叉搜索树的最近公共祖先_哔哩哔哩_bilibili思路:用之前一样的方法,哈哈哈哈哈,好处就是做出来了,但是我觉得需......
  • 二叉树的递归遍历和迭代遍历
    递归每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数,并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件:写完了递归算法,运行的时......
  • 代码随想录算法训练营第九天|LeetCode151.翻转字符串里的单词、卡码网:55.右旋转字符串
    前言打卡代码随想录算法训练营第49期第九天︿( ̄︶ ̄)︿首先十分推荐学算法的同学可以先了解一下代码随想录,可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解,卡哥清晰易懂的算法教学让我直接果断关注,也十分有缘和第49期的训练营大家庭一起进步。今日题目LeetCode151翻转字......
  • 代码随想录算法训练营 day37 day38| 卡码网52.完全背包 518. 零钱兑换 II 377.
    学习资料:https://programmercarl.com/背包问题理论基础完全背包.html#算法公开课相比于01背包,完全背包中每个物品都可以无限次的放入组合:先遍历物品,再逆序遍历背包排列:先逆序遍历背包,再遍历物品学习记录卡码网52.携带研究资料(dp[i]代表当重量为i时的最大价值)点击查看代码n......