网站策划建设方案书,徐州建站平台,手机上怎么做网站创业,找人做的网站怎么个人主页#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏#xff1a;http://t.csdnimg.cn/ZxuNL http://t.csdnimg.cn/c9twt 前言#xff1a;这个专栏主要讲述递归递归、搜索与回溯算法#xff0c;所以下面题目主要也是这些算法做的
我讲述…个人主页元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏http://t.csdnimg.cn/ZxuNL http://t.csdnimg.cn/c9twt 前言这个专栏主要讲述递归递归、搜索与回溯算法所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分 1、题目解析
2、算法原理思路讲解
3、代码实现 一、求根节点到叶节点数字之和
题目链接 求根节点到叶节点数字之和
题目
给你一个二叉树的根节点 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 二、解法
题目解析
这道题目的意思是给我们一棵二叉树让我们计算从根节点到叶节点生成的 所有数字之和 。
例如
示例 从根到叶子节点路径 4-9-5 代表数字 495
从根到叶子节点路径 4-9-1 代表数字 491
从根到叶子节点路径 4-0 代表数字 40
因此数字总和 495 491 40 1026 算法原理思路讲解
注意我们在做递归这一类题目是要将递归看作一个黑盒我们不管他是如何实现的我们就相信他一定可以帮助我们完成目标
递归思路 1、设计函数头寻找重复子问题并且将递归函数看作一个黑盒。
2、设计函数体只关心一个子问题并解决它
3、设计函数出口递归的终止条件 算法思路
根据题目意思可得我们可以使用一个前序遍历
在前序遍历的过程中我们可以往左右⼦树传递信息并且在回溯时得到左右⼦树的返回值。递归函数可以帮我们完成两件事 1.、将⽗节点的数字与当前节点的信息整合到⼀起计算出当前节点的数字然后传递到下⼀层进⾏递归 2、当遇到叶⼦节点的时候就不再向下传递信息⽽是将整合的结果向上⼀直回溯到根节点。 在递归结束时根节点需要返回的值也就被更新为了整棵树的数字和。 把上面翻译一下就是
例如对于节点9来说
1、节点9将⽗节点的数字4与自己的数字9结合在一起成49传递到下一层
2、当遇到节点5的时候就不再向下传递信息⽽是将整合的结果495返回 1、设计函数头
int dfs(TreeNode* root, int num)
1 返回值当前⼦树计算的结果数字和
2参数 num递归过程中往下传递的信息⽗节点的数字 3 函数作⽤整合⽗节点的信息与当前节点的信息计算当前节点数字并向下传递在回溯时返回当前⼦树当前节点作为⼦树根节点数字和。 2、设计函数体只关心一个子问题并解决它
当遇到空节点的时候说明这条路从根节点开始没有分⽀返回 0 结合⽗节点传下的信息以及当前节点的 val计算出当前节点数字 presum 如果当前结点不是叶⼦节点将 presum 传到左右⼦树中去得到左右⼦树中节点路径的数字和然后相加后返回结果。 presum presum * 10 root-val;int ret 0;
if(root-left) ret dfs(root-left, presum);
if(root-right) ret dfs(root-right, presum);
return ret; 3、设计函数出口 如果当前结点是叶⼦节点直接返回整合后的结果 presum
if(root-left nullptr root-right nullptr)return presum; 以上思路就讲解完了大家可以先自己先做一下 时间复杂度O(n)其中 n 是二叉树的节点个数。对每个节点访问一次。空间复杂度O(n)其中 n 是二叉树的节点个数。空间复杂度主要取决于递归调用的栈空间递归栈的深度等于二叉树的高度最坏情况下二叉树的高度等于节点个数空间复杂度为 O(n)。 代码实现
/*** 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 dfs(TreeNode* root, int presum){presum presum * 10 root-val;if(root-left nullptr root-right nullptr)return presum;int ret 0;if(root-left) ret dfs(root-left, presum);if(root-right) ret dfs(root-right, presum);return ret;}int sumNumbers(TreeNode* root) {return dfs(root,0);}
};
