左叶子之和&&从二叉搜索树到更大和树

举报
芒果_Mango 发表于 2022/11/30 23:48:22 2022/11/30
【摘要】 404.左叶子之和https://leetcode.cn/problems/sum-of-left-leaves/1.根节点不累加到结果中2.注意理解这里的左叶子的含义:这个是所有左边的叶子节点,并不是最左的结点,所以并不能使用层序遍历去拿到第一个左边的结点3.我们不能判断当前节点是不是左叶子只能判断当前节点是不是叶子(当前节点左为空&&右为空)必须通过其父节点来判断其左孩子是不是左叶子条...

404.左叶子之和

https://leetcode.cn/problems/sum-of-left-leaves/

1.根节点不累加到结果中
2.注意理解这里的左叶子的含义:这个是所有左边的叶子节点,并不是最左的结点,所以并不能使用层序遍历去拿到第一个左边的结点

3.我们不能判断当前节点是不是左叶子

  • 只能判断当前节点是不是叶子(当前节点左为空&&右为空)

必须通过其父节点来判断其左孩子是不是左叶子

  • 条件为:当前节点的左孩子不为空 && 左孩子的左孩子为空 && 左孩子的右孩子为空 就说明当前节点的左孩子是左叶子

image-20220522222445597


遍历整个二叉树,判断是否为左叶子,如果是就累加到sum中

核心代码:通过当前节点判断它的左孩子是不是左叶子root->left && root->left->left == nullptr&& root->left->right == nullptr

  • root->left !=nullptr 保证了当前节点有左孩子
  • root->left->left == nullptr &&root->left->right == nullptr : 说明当前节点的左孩子没有孩子->是叶子节点->是左叶子

同理:判断是不是右叶子:root->right&& root->right->right== nullptr&& root->right->left== nullptr

  • root->right!=nullptr 保证了当前节点有右孩子
  • root->right->left == nullptr &&root->right->right== nullptr : 说明当前节点的右孩子没有孩子->是叶子节点->是右叶子
class Solution {
public:
    int sum = 0;//统计左叶子的值的和,相当于是全局变量
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr) return 0;

        //问题所在:左叶子如何判断
        //根据父亲判断比较好!
        //如果当前节点的左孩子不为空 && 左孩子的左孩子为空 &&  左孩子的右孩子为空 就说明当前节点的左孩子是左叶子
        if(root->left && root->left->left == nullptr&& root->left->right == nullptr)
        {
            sum+=root->left->val;//累加当前节点的左孩子的值 (累加左叶子的值)
        }

        sumOfLeftLeaves(root->left);//去右树递归
        sumOfLeftLeaves(root->right);//去左树递归
        return sum;
    }
};

1038. 从二叉搜索树到更大和树

https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/

计算所有的大于等于当前结点val的所有结点val之和并替换,体现在BST中就是:该结点val+右子树val之和=>替换后的该结点的val

所以:先遍历右子树,然后是根节点,最后是左子树
这样我们只需要反序中序遍历该二叉搜索树,记录过程中的节点值之和,并不断更新当前遍历到的节点的节点值,即可得到题目要求的累加树

image-20220522232911150

class Solution {
public:
    int sum  = 0;//记录过程中的节点值之和
    TreeNode* bstToGst(TreeNode* root) {
        //反向走中序
        if(root == nullptr) return nullptr;
        bstToGst(root->right);//先递归右树
        
        //处理
        sum+=root->val;//sum累加当前节点的值   该节点的值 + 右子树的值->替换后的val
        root->val = sum;//更新节点的值为sum  
        
        bstToGst(root->left);//递归左树
        
        return root;
    }
};

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。