代码随想录额外题目| 二叉树 ●129求根到叶数字之和 ●1382二叉树变平衡●100相同的树

这篇具有很好参考价值的文章主要介绍了代码随想录额外题目| 二叉树 ●129求根到叶数字之和 ●1382二叉树变平衡●100相同的树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

#129求根到叶数字之和

回溯放进vector,然后从后往前拿,乘1 10 100 ... 很基础的回溯

my code:

    void backtrack(int depth, TreeNode* cur, vector<TreeNode*> &vec, int &sum){
        if(cur->left==nullptr &&cur->right==nullptr){
            size_t a=1;
            for(int i=vec.size()-1;i>=0;i--){
                sum+=vec[i]->val*a;
                a*=10;
            }
        
            return;
        }
        if(cur->left){
            vec.push_back(cur->left);
            backtrack(depth+1,cur->left, vec, sum);
            vec.pop_back();
        }
        if(cur->right){
            vec.push_back(cur->right);
            backtrack(depth+1,cur->right,vec, sum);
            vec.pop_back();
        }
    }

    int sumNumbers(TreeNode* root) {
        int sum=0;
        vector<TreeNode*> vec={root};
        
        backtrack(1,root,vec,sum);
        return sum;
    }

随想录跟我思路差不多,但这两个是放globa的:int result; vector<int> path; 最近总觉得global不安全不想放 

#1382二叉树变平衡

本来遇到这种会换root的就头疼,然后看了眼随想录,是要先变成vec,再从vec重构,就会了

mycode:

    vector<int> vec;

    void inorder(TreeNode* node){
        if(node==nullptr) return;
        inorder(node->left);
        vec.push_back(node->val);
        inorder(node->right);
    }

    TreeNode* build_tree(int start, int end){
        if(start>end) return nullptr;
        TreeNode* root= new TreeNode();
        int mid=(start+end)/2;
        int val=vec[mid];
        root->val=val;
        root->left=build_tree(start, mid-1);
        root->right=build_tree(mid+1, end);
        return root;
    }

    TreeNode* balanceBST(TreeNode* root) {
        inorder(root);
        return build_tree(0,vec.size()-1);
     
    }

#100相同的树 easy

以任何方式遍历比较即可:和随想录一模一样文章来源地址https://www.toymoban.com/news/detail-620210.html

    bool traverse(TreeNode* n1, TreeNode* n2){
        if(n1==nullptr && n2==nullptr) return true;
        if(n1==nullptr && n2) return false;
        if(n1 && n2==nullptr) return false;
        if(n1->val!=n2->val) return false;
        
        return traverse(n1->left, n2->left) && traverse(n1->right, n2->right);
    }

    bool isSameTree(TreeNode* p, TreeNode* q) {
        return traverse(p,q);
        
    }

到了这里,关于代码随想录额外题目| 二叉树 ●129求根到叶数字之和 ●1382二叉树变平衡●100相同的树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录 二叉树 Java(二)

    采用前序遍历的方式遍历该二叉树,然后统计该二叉树的节点个数 这种方式比较简单,但是没有利用题目中所给的完全二叉树这一信息 官方思路:二分查找+位运算 对于任意二叉树,都可以通过广度优先搜索或深度优先搜索计算节点个数,时间复杂度和空间复杂度都是O(n),

    2024年02月08日
    浏览(51)
  • 代码随想录二刷 |二叉树 | 二叉树的右视图

    199.二叉树的右视图 给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2: 输入: [1,null,3] 输出: [1,3] 示例 3: 输入: [] 输出: [] 提示: 二叉树的节点个数的范围是 [0,1

    2024年02月04日
    浏览(61)
  • 跟着《代码随想录刷题》(六)—— 二叉树

    LeetCode:114、二叉树的前序遍历 (1)递归法 (2)迭代法 (3)统一迭代格式 LeetCode:94、二叉树的中序遍历 (1)递归法 (2)迭代法 (3)统一迭代格式 LeetCode:145、二叉树的后序遍历 (1)递归法 (2)迭代法 (3)统一迭代格式 LeetCode:589、N叉树前序遍历 LeetCode:590、N叉

    2024年02月09日
    浏览(47)
  • 代码随想录day13 | 226.翻转二叉树 101.对称二叉树

    使用前、后序反转最为方便。 为啥不推荐中序? 中序遍历,某些节点的左右孩子会翻转两次,某些节点左右孩子不会被反转。 101.对称二叉树 关键在于,看这个节点对应的左子树和右子树是否可以相互反转。 1、如何比较呢? 比较的是两个子树的里侧和外侧的元素是否相等

    2024年02月15日
    浏览(39)
  • 1月3日代码随想录反转二叉树

    给你一棵二叉树的根节点  root  ,翻转这棵二叉树,并返回其根节点。 示例 1: 示例 2: 示例 3: 提示: 树中节点数目范围在  [0, 100]  内 -100 = Node.val = 100 这道题用递归的思想就是将根节点的左右儿子交换,然后再对子节点进行递归操作,直到子节点均为空。 但是我感觉

    2024年02月03日
    浏览(47)
  • 代码随想录day21(2)二叉树:二叉树的所有路径(leetcode257)

    题目要求:按任意顺序返回所有从根节点到叶节点的路径 思路:我们先递归地进行前序遍历,同时要注意回溯的过程,注意一些库的用法即可。 leetcode实战: 代码实现:

    2024年03月18日
    浏览(49)
  • 【代码随想录day21】二叉树的最近公共祖先

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 这题的难点在于: 如何建

    2024年02月15日
    浏览(44)
  • 【Day22-慢就是快】代码随想录-二叉树-迭代遍历

    用迭代法实现二叉树的前后中序遍历。 递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中 ,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。 此时大家应该知道我们用栈

    2024年02月10日
    浏览(47)
  • 【代码随想录day19】从前序与中序遍历序列构造二叉树

    使用递归建树,流程如下: 取出后序节点创建新树的节点 找到新树的节点在中序中的索引 分割中序序列 分割后序序列 继续递归建立整颗新树

    2024年02月15日
    浏览(34)
  • 代码随想录Day12 二叉树 LeetCode T102二叉树的层序遍历 T226 翻转二叉树 T101 对称二叉树

    本文思路和详细讲解来自于:代码随想录 (programmercarl.com) 题目链接:102. 二叉树的层序遍历 - 力扣(LeetCode) 本题使用队列辅助完成,讲解主要函数CheckOrder:首先判断root是否为空,是就直接返回,然后创建队列,向里加入root元素,计算队列的长度,也就是每一层的元素个数,while循环,si

    2024年02月06日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包