首页 > 其他分享 >力扣 129. 求根节点到叶节点数字之和

力扣 129. 求根节点到叶节点数字之和

时间:2022-11-02 15:24:28浏览次数:91  
标签:return cur curSum work 求根 力扣 root 节点

129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字:

  • 例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1:

输入:root = [1,2,3]
输出:25
解释:
从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此,数字总和 = 12 + 13 = 25

示例 2:

输入:root = [4,9,0,5,1]
输出:1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491 从根到叶子节点路径 4->0 代表数字 40 因此,数字总和 = 495 + 491 + 40 = 1026

提示:

  • 树中节点的数目在范围 [1, 1000] 内
  • 0 <= Node.val <= 9
  • 树的深度不超过 10

题解

使用递归完成dfs,每次遍历到当前节点时,通过变量curSum根节点到当前节点的和,在每次遍历加入子节点时,当前和就乘以10+子节点的值。如果是叶子节点就记录并停止递归。

查看代码
 class Solution {
public:
    int allSum=0;
    void work(TreeNode* cur,int curSum){//cur当前节点,curSum根节点到当前节点的和
        if(cur->left==nullptr&&cur->right==nullptr){//如果是叶子节点就记录并停止递归
            allSum+=curSum;
            return;
        }
        if(cur->left)
            work(cur->left,curSum*10+cur->left->val);
        if(cur->right)
            work(cur->right,curSum*10+cur->right->val);
    }
    int sumNumbers(TreeNode* root) {
        if(root==nullptr)
            return 0 ;
        work(root,root->val);
        return allSum;
    }
};

也有不使用遍历记录和的写法。

查看代码
 class Solution {
public:
    int work(TreeNode* cur,int curSum){
        if(cur==nullptr)
            return 0;
        curSum=curSum*10+cur->val;
        if(cur->left==nullptr&&cur->right==nullptr){
            return curSum;
        }
        return work(cur->left,curSum)+work(cur->right,curSum);
    }
    int sumNumbers(TreeNode* root) {
        if(root==nullptr)
            return 0 ;
        return work(root,0);
    }
};

标签:return,cur,curSum,work,求根,力扣,root,节点
From: https://www.cnblogs.com/fudanxi/p/16851090.html

相关文章

  • leetcode222-完全二叉树的节点个数
    222.完全二叉树的节点个数这道题如果要最快,就要充分利用完全二叉树的性质。甚至还有二分查找法,还没怎么认真看利用树的深度判断是否为完全二叉树。若是,直接公式得出节......
  • 力扣-147-对链表进行插入排序
    ListNode*insertionSortList(ListNode*head){ //待排节点需要和它前面的节点比较?单链表怎么比,单链表的反向遍历? //只能从头开始找 //还要手写链表的交换? if(!he......
  • K8S节点配置资源驱逐
    当节点内存到达多少时。对节点的pod进行驱逐[root@lecode-test-001~]#cat/var/lib/kubelet/kubeadm-flags.envKUBELET_KUBEADM_ARGS="--network-plugin=cni--pod-inf......
  • 记一次node节点无法加入K8S集群
    #问题现象:root@small-virtual-machine:~#kubeadmjoin10.0.0.133:6443--tokend2hyl5.5qt5fzjsdbxm2k5o   --discovery-token-ca-cert-hashsha256:d02674df33b......
  • Javascript进阶笔记 - DOM模型与节点
    DOM模型与节点目录DOM模型与节点1.DOM模型2.节点2.1节点的常用方法1.DOM模型DOM(文档对象模型)就是把文档中的标签,属性,文本转换成对象来管理(类似于Java中的对象)do......
  • 力扣 124. 二叉树中的最大路径和 [1.0,2.0]
    124.二叉树中的最大路径和路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 ......
  • 动力节点——day07
    什么是异常?异常是指在程序的运行过程中所发生的不正常的事件,它会中断正在运行的程序Java中异常的存在形式?异常在java中以类的形式存在,每一个异常类都可以创建异常......
  • Jenkins Pipeline 流水线 - 添加节点 使用代理
    Jenkins安装在Windows上Docker在Linux上流程将Docker在Jenkins节点中维护Pipeline中指定某些阶段使用哪个节点添加节点CheckingJavaversionint......
  • 代码随想录算法训练营第四天 |24. 两两交换链表中的节点 19.删除链表的倒数第N个节点
    摆了两天,开始赶进度。一开始没太理解这个递归的含义,后来理解成了从后往前将链表两两拆分之后进行操作环型链表还不太理解缺面试题链表相交 24.两两交换链表中的节......
  • 力扣 113. 路径总和 II [dfs,bfs]
    113.路径总和II给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点是指没有子节......