LeetCode 129.Sum Root to Leaf Numbers (求根到叶子节点数字之和)

Love The Way You Lie 2022-05-08 06:04 290阅读 0赞

题目描述：

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

  1. 输入: [1,2,3]
  2.     1
  3.    / \
  4.   2   3
  5. 输出: 25
  6. 解释:
  7. 从根到叶子节点路径 1->2 代表数字 12.
  8. 从根到叶子节点路径 1->3代表数字 13.
  9. 因此，数字总和 = 12 + 13 = 25.

示例 2:

  1. 输入: [4,9,0,5,1]
  2.     4
  3.    / \
  4.   9   0
  5.  / \
  6. 5   1
  7. 输出: 1026
  8. 解释:
  9. 从根到叶子节点路径 4->9->5 代表数字 495.
  10. 从根到叶子节点路径 4->9->1 代表数字 491.
  11. 从根到叶子节点路径 4->0 代表数字 40.
  12. 因此，数字总和 = 495 + 491 + 40 = 1026.

AC C++ Solution:

DFS算法：每到达叶节点，进行累加

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     int sumNumbers(TreeNode* root) {
  13.         if(!root)
  14.             return 0;
  16.         int currentSum = 0;
  17.         sum = 0;
  18.         DFS(root,currentSum);
  19.         return sum;
  20.     }
  22.     void DFS(TreeNode *node, int currentSum) {
  23.         currentSum = currentSum*10 + node->val;
  24.         if(!node->left && !node->right)
  25.             sum += currentSum;
  27.         if(node->left)
  28.             DFS(node->left,currentSum);
  29.         if(node->right)
  30.             DFS(node->right,currentSum);
  31.     }
  33. private:
  34.     int sum;    
  35. };

发表评论

表情：
评论列表 （有 0 条评论，290人围观）

还没有评论，来说两句吧...

相关阅读