代码编织梦想

Leetcode110平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

输入:root = [3,9,20,null,null,15,7]
输出:true

思考:

  • 递归以空节点返回0为终止条件,表示当前节点树的高度为0
  • 当当前不是平衡子树的时候返回-1,子树即整棵树都不是平衡树

/**
 * 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 getHeight(TreeNode* node)
    {
        if(node==nullptr) return 0;  //递归终止条件
        //采用后序遍历 左右中(不采用前序的原因是因为要先得到左和右才能在中节点比较)
        int leftHeight = getHeight(node->left);
        if(leftHeight==-1) return -1;
        
        int rightHeight = getHeight(node->right);
        if(rightHeight==-1) return -1;
        
        if(abs(leftHeight-rightHeight)>1) return -1;
        else
            return 1+max(leftHeight,rightHeight);
        
    }
    bool isBalanced(TreeNode* root) {
    return getHeight(root)==-1 ? false : true;
    }
};

257二叉树的所有路径

给定一个二叉树,返回所有从根节点到叶子节点的路径。

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

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

思考:

  • 递归完做回溯的时候要先删节点才能加入新的节点
  • 递归和回溯要放在一起,不能拆开
/**
 * 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:
    void traversal(TreeNode* cur,vector<int>&path,vector<string>&result)
    {
        //前序遍历中左右
        path.push_back(cur->val);   //中 最后一个节点也要加入
        if(cur->left ==nullptr && cur->right ==nullptr)
        {
             string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if(cur->left) {
            traversal(cur->left,path,result);
            path.pop_back(); //弹出 回溯
        }
         if (cur->right) { // 右
            traversal(cur->right, path, result);
            path.pop_back(); // 回溯
        }
    }

    
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

404. 左叶子之和

给定二叉树的根节点 root ,返回所有左叶子之和。

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
/**
 * 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 sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right== NULL) return 0;

        int leftValue = sumOfLeftLeaves(root->left);    // 左
        if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况
            leftValue = root->left->val;
        }
        int rightValue = sumOfLeftLeaves(root->right);  // 右

        int sum = leftValue + rightValue;               // 中
        return sum;
    }
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44640001/article/details/128841538

leetcode 110. 平衡二叉树_却顾所来径的博客-爱代码爱编程

题目描述:   给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。

leetcode257. 二叉树的所有路径_吃西瓜要吐米米的博客-爱代码爱编程

给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

leetcode404. 左叶子之和_吃西瓜要吐米米的博客-爱代码爱编程

计算给定二叉树的所有左叶子之和。 示例: 3 / \ 9 20 / \ 15 7 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24   思路:定义全局变量sum=0,深度优先遍历二叉树,当结点为左叶子结点时,sum加上该结点的值。(重点是判断该结点是

leetcode404. 左叶子之和 (二叉树递归)-爱代码爱编程

https://leetcode-cn.com/problems/sum-of-left-leaves/ 计算给定二叉树的所有左叶子之和。 示例: 3 / 9 20 / 15 7 在这个二叉树中,有两个左叶子,分别是 9

leetcode 题目-257.二叉树的所有路径/404.左叶子节点之和(python实现)_彬小二的博客-爱代码爱编程

作为要准备踏入码农行业的人来说,要准备校招,怎么能不去刷刷LeetCode呢? 257.二叉树的所有路径 题目要求 给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 例如

【LeetCode算法修炼+动画演示】【二叉树的路径和】——404. 左叶子之和-爱代码爱编程

404. 左叶子之和 原题链接 计算给定二叉树的所有左叶子之和。 示例: 3 / \ 9 20 / \ 15 7 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24 要点 与【LeetCode算法修炼指南】——112.路径总和、113.路径总和II 是类型相同的题目 不同的点在于这里的终

二叉树简单 LeetCode404. 左叶子之和 NC248 左叶子之和-爱代码爱编程

404. 左叶子之和 描述 计算给定二叉树的左叶子之和。 树上叶子节点指没有后继节点的节点,左叶子指连向父节点的左侧的叶子节点。 import java.util.*; public class Solution { int sum = 0; public int sumOfLeftLeaves (TreeNode root) {

【二叉树】404. 左叶子之和-爱代码爱编程

题目: 计算给定二叉树的所有左叶子之和。 示例: 题解: 注意是判断左叶子,不是二叉树左侧节点! 步骤: 1.确定递归函数的参数和返回值 判断一个树的左叶子节点之和,那么一定要传入树的根节点,递归函数的返回值为数值之和,所以为int,使用题目中给出的函数就可以了。 2.确定终止条件 root为空则返回 3.确定单层递归的逻辑 当遇

leetcode刷题day17|110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和_霍格沃兹程序员的博客-爱代码爱编程

文章目录 一、110.平衡二叉树二、257.二叉树的所有路径三、404.左叶子之和 一、110.平衡二叉树 刚开始写这道题,没有太明确的思路。但是,硬着头皮往下写还是有可能写出正确答案的。 我使用的是递归法。

代码随想录算法训练营第17天 | 110. 平衡二叉树,257. 二叉树的所有路径,404. 左叶子之和_p_m_h的博客-爱代码爱编程

代码随想录算法训练营第17天 | 110. 平衡二叉树,257. 二叉树的所有路径,404. 左叶子之和 110. 平衡二叉树 左右子树高度差不大于1 就是平衡二叉树递归三部曲 终止条件 node==null 高度为0

代码随想录算法训练营第十七天| leetcode110. 平衡二叉树、leetcode257. 二叉树的所有路径、leetcode404. 左叶子之和_喵的博客-爱代码爱编程

一、LeetCode110. 平衡二叉树         1:题目描述(110. 平衡二叉树) 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。           2:解题思路 # Definition for a binary tree

代码随想录算法训练营第十七天| lc110. 平衡二叉树、lc257. 二叉树的所有路径、lc404. 左叶子之和_溪岚cw的博客-爱代码爱编程

LeetCode 110 平衡二叉树 题目链接:110. 平衡二叉树 做题情况:独立做本题时候看到就很懵,不知到从何处下手,想写出递归写法可是不知道咋样写出来,看完卡哥视频和代码随想录书相关部分后,才知道也要严格按照递归

代码随想录算法训练营day17|leetcode110平衡二叉树、leetcode257二叉树的所有路径、leetcode404左叶子之和-爱代码爱编程

Day17打卡! 时长:1.5h 今日感想:今天也是收获满满!前两天的内容得到复习的基础上,还学到了新的解题思路~ Leetcode110 平衡二叉树 题目链接:Leetcode110 平衡二叉树 第一想法:感觉跟昨天做的题有点像,也是处理高度的活,应该要用后序遍历。 讲解后想法: 递归三部曲(后序) 1.明确递归函数的

代码随想录no17 |leetcode 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和-爱代码爱编程

二叉树第四天_110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和 今天开始第四天的二叉树,内容有点多,估计年前能结束二叉树。 110.平衡二叉树 给定一个二叉树,判断它是否是高度平衡的二叉树。

代码随想录算法训练营第十七天 | leetcode 110. 平衡二叉树,257. 二叉树的所有路径,404.左叶子之和-爱代码爱编程

代码随想录算法训练营第十七天 | leetcode 110. 平衡二叉树,257. 二叉树的所有路径,404.左叶子之和 110. 平衡二叉树257. 二叉树的所有路径404.左叶子之和 110. 平衡二叉树

代码随想录算法训练营第十七天| 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和-爱代码爱编程

Leetcode 110.平衡二叉树 思路分析: 是否是平衡二叉树取决于左右子树的高度相差是否大于1,可用递归法求取左右子树的高度,如果存在左右子树高度超过1,则该二叉树一定不是平衡二叉树。递归终止条件是遍历到叶子节点。 代

代码随想录算法训练营day17| 104.二叉树的最大深度、257. 二叉树的所有路径、404.左叶子之和-爱代码爱编程

Leetcode 104.二叉树的最大深度 题目链接 思路:递归法,后序遍历,求二叉树的高度 代码: class Solution { public boolean isBalanced(TreeNode roo