求一个二叉树所有从根节点到叶子结点构成的字符串转为数字之后的数值之和,简单DFS/BFS
Python版——DFS
1 #129
2 #Runtime: 20 ms (Beats 46.49%)
3 #Memory: 13.4 MB (Beats 79.53%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def sumNumbers(self, root):
13 """
14 :type root: TreeNode
15 :rtype: int
16 """
17 self.ans = 0
18 def DFS(node, t):
19 if not node:
20 return
21 if node.left or node.right:
22 DFS(node.left, t * 10 + int(node.val))
23 DFS(node.right, t * 10 + int(node.val))
24 else:
25 self.ans += t * 10 + int(node.val)
26 return
27
28 DFS(root, 0)
29 return self.ans
C++版——BFS
1 //129
2 //Runtime: 24 ms (Beats 19.15%)
3
4 /**
5 * Definition for binary tree
6 * struct TreeNode {
7 * int val;
8 * TreeNode *left;
9 * TreeNode *right;
10 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11 * };
12 */
13 class Solution {
14 public:
15 struct Que {
16 int s;
17 TreeNode *p;
18 }q[100010];
19
20 int sumNumbers(TreeNode *root) {
21 int l = 0, r = 1, res = 0;
22 if(root == NULL) return 0;
23 q[0].p = root;
24 q[0].s = root->val;
25 while(l < r) {
26 if(q[l].p->left == NULL && q[l].p->right == NULL) {
27 res += q[l].s;
28 }
29 if(q[l].p->left != NULL) {
30 q[r].p = q[l].p->left;
31 q[r].s = q[l].s * 10 + q[r].p->val;
32 ++r;
33 }
34 if(q[l].p->right != NULL) {
35 q[r].p = q[l].p->right;
36 q[r].s = q[l].s * 10 + q[r].p->val;
37 ++r;
38 }
39 ++l;
40 }
41 return res;
42 }
43 };