Leetcode 872 Leaf-Similar Trees

发表于 |

分析：

  1. 一棵树的叶子节点的值从左至右构成的序列叫做叶子序列
  2. 判断两颗树的叶子序列是否相同
  3. 显然要处理不同层的叶子还要从左至右，肯定是dfs了

思路：

  1. 编写dfs()用于遍历树，并记录叶子序列
  2. 对两棵树分别调用dfs函数，比较叶子序列是否相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def leafSimilar(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: bool
        """
        def dfs(root,rec):
            if not root.left and not root.right:
                rec.append(root.val)
            if root.left:
                dfs(root.left,rec)
            if root.right:
                dfs(root.right,rec)
        rec1, rec2 = [], []
        dfs(root1, rec1)
        dfs(root2, rec2)
        return rec1 == rec2

36 / 36 test cases passed.
diffculty: easy
Runtime: 28 ms