网站地址和网页地址,承德网站建设怎么建设的,小程序app软件开发公司,微博推广方式1. 题目链接#xff1a;129. 求根节点到叶节点数字之和
2. 题目描述#xff1a; 给你一个二叉树的根节点 root #xff0c;树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字#xff1a; 例如#xff0c;从根节点到叶节点的路径 1…1. 题目链接129. 求根节点到叶节点数字之和
2. 题目描述 给你一个二叉树的根节点 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 3. 解法前序遍历
前序遍历的顺序为根结点-左子树-右子树
3.1 算法思路
在前序遍历的过程中我们可以往左右子树传递信息并且在回溯时得到左右子树的返回值。递归函数可以帮助我们完成两件事情
将父节点的数字与当前节点的信息整合到一起计算出当前节点的数字然后传递到下一层进行递归当遇到叶子节点的时候就不再向下传递信息而是将整合的结果向上一种回溯到根节点
在递归结束时根节点需要返回的值也就被更新为了整棵树的数字之和
3.2 算法流程
递归函数设计int dfsTreeNode* rootint num)
返回值当前子树计算的结果数字和参数num递归过程中往下传递的信息父节点的数字函数作用整合父节点的信息与当前节点的信息计算当前节点数字并向下传递在回溯时返回当前子树当前节点作为子树根节点数字和。
递归函数流程
当遇到空节点的时候说明这条路从根节点开始没有分支返回0结合父节点传下的信息以及当前节点的val计算出当前节点数字num如果当前节点是叶子节点直接返回整合后的结果num如果当前节点不是叶子节点将num传到左右子树中去得到左右子树节点路径的数字和然后相加后返回结果 3.3 C算法代码
/*** 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 sumNumbers(TreeNode* root) {return dfs(root,0);}int dfs(TreeNode*root,int num){numnum*10root-val;//如果左右子树为空说明是没有左右子树返回numif(root-leftnullptrroot-rightnullptr)return num;int ret0;if(root-left)retdfs(root-left,num);if(root-right)retdfs(root-right,num);return ret;}
};
