Leaf-Similar Trees
环境：python 3.6，scala 2.11.8
题意
一棵二叉树上所有叶子的值，按从左到右的顺序排列形成一个 叶值序列 。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
分析
判断两棵二叉树的叶值序列是否相等，要求有序。
-
要点
遍历过程中只需添加叶子结点，确定添加条件即可；
要求从左到右，前中后序都可保证左子树的叶子结点比右子树的叶子结点先被添加；
后续代码主要参考前序遍历代码思路；
将可迭代对象打包成元组，元素未对齐时用空值填充：zip函数是以最少元素为准，而 itertools.zip_longes 以最多元素为准；
代码
python
import itertools
def leafSimilar(root1, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
return sup(root1) == sup(root2)
# return supV2(root1) == supV2(root2)
# return supV3(root1) == supV3(root2)
# 这里前中后序 + BFS/DFS 都可
def sup(root):
r = []
def dfs(node):
if node:
if not node.left and not node.right:
r.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return r
# 前序遍历示例
def supV2(root):
if not root: return []
curr = [root.val] if not root.left and not root.right else []
return curr + supV2(root.left) + supV2(root.right)
# 前序遍历示例
def supV3(root):
if not root: return []
r = []
stack = [root]
while stack:
curr = stack.pop()
if curr:
if not curr.left and not curr.right:
r.append(curr.val)
stack.append(curr.right)
stack.append(curr.left)
return r
def leafSimilarV2(root1, root2):
def dfs(node):
if node:
if not node.left and not node.right:
yield node.val
for chid in dfs(node.left): yield chid
for chid in dfs(node.right): yield chid
return all(a == b for a, b in itertools.zip_longest(dfs(root1), dfs(root2))) # 迭代器
scala
import scala.collection.mutable.{ListBuffer, Stack}
object LC872 {
def leafSimilar(root1: TreeNode, root2: TreeNode): Boolean = {
sup(root1) == sup(root2)
// supV2(root1) == supV2(root2)
// supV3(root1) == supV3(root2)
}
/** 修改添加节点值的条件，解法与 LC144 一致 */
def sup(root: TreeNode): List[Int] = {
val r = ListBuffer.empty[Int]
def dfs(node: TreeNode): Unit =
if (node != null) {
if (node.left == null & node.right == null)
r += node.value
dfs(node.left)
dfs(node.right)
}
dfs(root)
r.toList
}
def supV2(root: TreeNode): List[Int] = root match {
case null => Nil
case node: TreeNode =>
val curr: List[Int] = if (node.left == null & node.right == null) List(node.value) else Nil
curr ::: supV2(node.left) ::: supV2(node.right)
}
def supV3(root: TreeNode): List[Int] = {
if (root == null) return Nil
val r = ListBuffer.empty[Int]
val stack = Stack[TreeNode](root)
while (stack.nonEmpty) {
val node = stack.pop()
if (node != null) {
if (node.left == null & node.right == null)
r += node.value
stack.push(node.right)
stack.push(node.left)
}
}
r.toList
}
}
最后
欢迎交流和补充
