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,遇到叶子就记录值,一开始想当然的所有数字转string拼一起,但是这样不能区分6 17 4和6 1 7 4,所以每次拼接的时候数值左右两边各多加一个空格

 1 #872
 2 #Runtime: 36 ms
 3 #Memory: 13.5 MB
 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 leafSimilar(self, root1, root2):
13         """
14         :type root1: TreeNode
15         :type root2: TreeNode
16         :rtype: bool
17         """
18         def DFS(r):
19             if not r:
20                 return ''
21             if not r.left and not r.right:
22                 return ' ' + str(r.val) + ' '
23             return DFS(r.left) + DFS(r.right)
24         return DFS(root1) == DFS(root2)

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