NC5 二叉树根节点到叶子节点的所有路径和

vlambda
2021-07-21

NC5 二叉树根节点到叶子节点的所有路径和

情景提要

牛客题解系列，按照题号顺序开始。

NC5 二叉树根节点到叶子节点的所有路径和

题目描述

输入输出示例

输入:

{1,0}

输出:

题目分析

对于二叉树的题目，一般来说，都有迭代和递归两种方法可以解决。

需要思考对二叉树的遍历方式。如本题，从根节点开始，依次向下遍历即可。也就是中左右或者中右左。

按照习惯，采样前序遍历。

思路1

采用递归进行遍历。

需要考虑递归函数何时返回？传递到参数有哪些?

访问到叶子结点就返回啦。至于传递参数，在写的过程中，就慢慢补上了。

这里有两种方法，一种是定义一个中间变量，利用回溯，来记录到当前结点的数字，另一种是将数字直接存在当前结点的数值上。本篇就先采用第二种啦。

思路2

本题中，可以使用队列进行层序遍历，较简单些。当然，采用栈来模拟也能写出来，小伙伴们可以自己去尝试下哦。

代码实现

方法1

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */class Solution {public: /** *  * @param root TreeNode类  * @return int整型 */ int res = 0; int sumNumbers(TreeNode* root) { // write code here if(!root) return 0; travel(root, 0); return res; } void travel(TreeNode* node,int sum){ node->val += sum * 10; if(node->left) { travel(node->left, node->val); } if(node->right) { travel(node->right, node->val); }else if(!node->left){ res += node->val; } }};

方法2

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
class Solution {public: /** *  * @param root TreeNode类  * @return int整型 */ //用队列模拟 int sumNumbers(TreeNode* root) { // write code here int res = 0; queue<TreeNode*> q; if(root) q.push(root); TreeNode* node; while(!q.empty()){ int n=q.size(); for(int i=0;i<n;++i){ node = q.front(); q.pop(); if(node->left){ node->left->val += node->val*10; q.push(node->left); } if(node->right){ node->right->val += node->val*10; q.push(node->right); }else if(!node->left){ res += node->val; } } } return res; }};