题目

请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

提示：

给定的两颗树可能会有 1 到 100 个结点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/leaf-similar-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

• 首先要判断是不是叶子节点，用于记录叶子节点
• 获得第一颗树的叶子序列，获得第二颗的叶子序列
• 比较序列

代码

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

class Solution(object):
    def leafSimilar(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: bool
        """
        if not root1 and root2:
            return False
        if not root2 and root1:
            return False
        if not root1 and not root2:
            return True
        
        def isLeaf(node):
            if node.left == None and node.right == None:
                return True
            else:
                return False
        
        def leafOrder(node):
            order = []
            if not node:
                return []
            if isLeaf(node):
                order.append(node.val)
            order.extend(leafOrder(node.left))
            order.extend(leafOrder(node.right))
            return order
        
        order1 = leafOrder(root1)
        order2 = leafOrder(root2)
        
        if len(order1) != len(order2):
            return False
        else:
            for i in range(len(order1)):
                if order1[i] != order2[i]:
                    return False
        return True