本文共 2540 字，大约阅读时间需要 8 分钟。

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123 . Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]    1   / \  2   3Output: 25Explanation:The root-to-leaf path 1->2 represents the number 12.The root-to-leaf path 1->3 represents the number 13.Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]    4   / \  9   0 / \5   1Output: 1026Explanation:The root-to-leaf path 4->9->5 represents the number 495.The root-to-leaf path 4->9->1 represents the number 491.The root-to-leaf path 4->0 represents the number 40.Therefore, sum = 495 + 491 + 40 = 1026.

题意：给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123 。计算从根到叶子节点生成的所有数字之和。

思路1 递归先序搜索

先序遍历，计算和即可。代码如下：

class Solution {
   public:     int getAllNumbers(TreeNode* root, int num) {
           if (!root) return 0;        if (!root->left && !root->right) return num * 10 + root->val;        int val = num * 10 + root->val;        return getAllNumbers(root->left, val) + getAllNumbers(root->right, val);    }    int sumNumbers(TreeNode* root) {
           return getAllNumbers(root, 0);    }};

效率如下：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗：12.2 MB, 在所有 C++ 提交中击败了34.94% 的用户

20201029 Update 如果使用原函数的话，可以写成如下形式：

class Solution {
   public:    int sum = 0, num = 0;    int sumNumbers(TreeNode* root) {
           if (root == nullptr) return 0;        num = num * 10 + root->val;        if (root->left == nullptr && root->right == nullptr) sum += num;        sumNumbers(root->left);        sumNumbers(root->right);        num /= 10; //回溯到上一层        return sum;    }};

效率不是很好：

执行用时：8 ms, 在所有 C++ 提交中击败了35.13% 的用户内存消耗：12.4 MB, 在所有 C++ 提交中击败了28.99% 的用户

思路2 非递归先序遍历

实际代码如下：

class Solution {
   public:     int sumNumbers(TreeNode* root) {
           stack
   
     st;        int sum = 0;        TreeNode *temp = root;        while (temp || !st.empty()) {
               while (temp) {
                   st.push(temp);                if (temp->left) temp->left->val += temp->val * 10; //修改原树上的值                temp = temp->left;            }            temp = st.top(); st.pop();            if (!temp->left && !temp->right) sum += temp->val; //遇到叶子节点            if (temp->right) temp->right->val += temp->val * 10; //修改原树上的值            temp = temp->right;        }        return sum;    }};
   

效率如下：

执行用时：8 ms, 在所有 C++ 提交中击败了34.87% 的用户内存消耗：12.2 MB, 在所有 C++ 提交中击败了36.07% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108923555 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！