题意

一棵二叉树上所有叶子的值，按从左到右的顺序排列形成一个 叶值序列 。

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

分析

判断两棵二叉树的叶值序列是否相等，要求有序。

基础：二叉树的前、中、后序遍历；
要点
- 遍历过程中只需添加叶子结点，确定添加条件即可；
- 要求从左到右，前中后序都可保证左子树的叶子结点比右子树的叶子结点先被添加；
- 后续代码主要参考前序遍历代码思路；
- 将可迭代对象打包成元组，元素未对齐时用空值填充：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
  }
}