# 872. Leaf-Similar Trees 叶子相似的树

@TOC

## # 题目描述

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

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

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

Return `true` if and only if the two given trees with head nodes `root1` and `root2` are leaf-similar.

Note:

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

## # 解题方法

### # 中序遍历

``````# 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, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
leaves1 = []
leaves2 = []
self.inOrder(root1, leaves1)
self.inOrder(root2, leaves2)
return leaves1 == leaves2

def inOrder(self, root, leaves):
if not root:
return
self.inOrder(root.left, leaves)
if not root.left and not root.right:
leaves.append(root.val)
self.inOrder(root.right, leaves)
``````

### # 先序遍历

``````# 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, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
return self.getLeafs(root1) == self.getLeafs(root2)

def getLeafs(self, root):
res = []
if not root:
return res
if not root.left and not root.right:
return [root.val]
res.extend(self.getLeafs(root.left))
res.extend(self.getLeafs(root.right))
return res
``````

``````# 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, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
return self.preOrder(root1) == self.preOrder(root2)

def preOrder(self, root):
stack = []
stack.append(root)
res = []
while stack:
node = stack.pop()
if not node: continue
if not node.left and not node.right:
res.append(node.val)
stack.append(node.left)
stack.append(node.right)
return res
``````

### # 后序遍历

``````# 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, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
return self.postOrder(root1) == self.postOrder(root2)

def postOrder(self, root):
stack = []
stack.append(root)
res = []
while stack:
node = stack.pop()
if not node: continue
stack.append(node.left)
stack.append(node.right)
if not node.left and not node.right:
res.append(node.val)
return res
``````

## # 日期

2018 年 8 月 16 日 —— 一个月不写题，竟然啥都不会了。。加油！ 2018 年 11 月 7 日 —— 天冷加衣！