Sum Root to Leaf Numbers - LeetCode

概述目录 题目链接 注意点 解法 小结 题目链接 Sum Root to Leaf Numbers - LeetCode 注意点 不要访问空结点 解法 **解法一：递归。sum表示从root到当前节点的值的和，ret是所有路径和。如果没有左右儿子说明是叶子节点，就把sum加到ret，否则把当前的sum*10加上自己的值。** /** * Definition for a binary tree no

目录

题目链接 注意点 解法 小结 题目链接

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所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。