Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
求一个二叉树所有从根节点到叶子结点构成的字符串转为数字之后的数值之和,简单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 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理