求一個(gè)二叉樹所有從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)構(gòu)成的字符串轉(zhuǎn)為數(shù)字之后的數(shù)值之和，簡(jiǎn)單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 };