Leaf-Similar Trees

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form aleaf value sequence.

For example, in the given tree above, the leaf value sequence is(6, 7, 4, 9, 8).

Two binary trees are consideredleaf-similar if their leaf value sequence is the same.

Returntrueif and only if the two given trees with head nodesroot1androot2are leaf-similar.

Note:

• Both of the given trees will have between 1 and 100 nodes.

分析

dfs返回叶子列表

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:

        def dfs(root):
            if not root:
                return []
            if not root.left and not root.right:
                return [root.val]

            return dfs(root.left) + dfs(root.right)
        return dfs(root1) == dfs(root2)