大佬教程收集整理的这篇文章主要介绍了Sum Root to Leaf Numbers - LeetCode,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
Sum Root to Leaf Numbers - LeetCode
**解法一:递归。sum表示从root到当前节点的值的和,ret是所有路径和。如果没有左右儿子说明是叶子节点,就把sum加到ret,否则把当前的sum*10加上自己的值。**
/** * DeFinition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int X) : val(X),left(NULL),right(NULL) {} * }; */ class Solution { public: int sumnumbers(TreeNode* root) { int ret = 0; sumnumbers(root,ret); return ret; } void sumnumbers(TreeNode* root,int sum,int& ret) { if(!root) return; sum = sum*10+root->val; if(root->left) sumnumbers(root->left,sum,ret); if(root->right) sumnumbers(root->right,ret); if(!root->left && !root->right) ret += sum; } };
**解法二:非递归,bfs。将自己的节点值*10加到儿子节点上,如果是叶子节点就把自己的值加到ret上(因为已经更新过了,自己的值就是路径上节点值的和)**
/** * DeFinition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int X) : val(X),right(NULL) {} * }; */ class Solution { public: int sumnumbers(TreeNode* root) { int ret = 0; if(!root) return ret; queue<TreeNode*> q; q.push(root); while(!q.empty()) { TreeNode* t = q.front();q.pop(); if(t->left) { t->left->val = t->val*10+t->left->val; q.push(t->left); } if(t->right) { t->right->val = t->val*10+t->right->val; q.push(t->right); } if(!t->left && !t->right) ret += t->val; } return ret; } };
以上是大佬教程为你收集整理的Sum Root to Leaf Numbers - LeetCode全部内容,希望文章能够帮你解决Sum Root to Leaf Numbers - LeetCode所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。