跳至主要內容

0872. 叶子相似的树

ITCharge小于 1 分钟

0872. 叶子相似的树open in new window

  • 标签:树、深度优先搜索、二叉树
  • 难度:简单

题目链接

题目大意

将一棵二叉树树上所有的叶子,按照从左到右的顺序排列起来就形成了一个「叶值序列」。如果两棵二叉树的叶值序列是相同的,我们就认为它们是叶相似的。

现在给定两棵二叉树的根节点 root1root2。如果两棵二叉是叶相似的,则返回 True,否则返回 False

解题思路

分别 DFS 遍历两棵树,得到对应的叶值序列,判断两个叶值序列是否相等。

代码

class Solution:
    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
        def dfs(node: TreeNode, res: List[int]):
            if not node:
                return
            if not node.left and not node.right:
                res.append(node.val)
            dfs(node.left, res)
            dfs(node.right, res)

        res1 = []
        dfs(root1, res1)
        res2 = []
        dfs(root2, res2)
        return res1 == res2