题目
请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如上图所示，给定一颗叶值序列为 (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
