LeetCode 100.相同的树 python/scala

Same Tree

环境：python 3.6，scala 2.11.8

题意

判断两颗二叉树是否相同（结构相同 + 各节点值相同）。

分析

首先，题意非常明确：当两颗树结构相同、各节点值相同时，则称这两棵树相同。因此，用集合装载节点值、判断集合中元素值是否相同无法通过，它无法判断结构是否相同。

• 基础：掌握树的先序、中序、后序三种遍历方式（DFS/BFS 方法）；

• 选定上述一种遍历方式后，可在遍历过程中判断：

  • 两颗树只有其中一颗树有子节点，则说明两树不同；

  • 两个树都有子节点：

    • 节点值不同，则说明两树不同；

    • 节点值相同，继续遍历；

代码

python

def isSameTree(p, q):
    """
    :type p: TreeNode
    :type q: TreeNode
    :rtype: bool
    """
    def dfs(node1, node2):
        if not node1 and not node2: return True
        if not node1 or not node2: return False
        return node1.val == node2.val and dfs(node1.left, node2.left) and dfs(node1.right, node2.right)
    return dfs(p, q)


def isSameTreeV2(p, q):
    if not p and not q: return True
    if not p or not q: return False
    return p.val == q.val and isSameTreeV2(p.left, q.left) and isSameTreeV2(p.right, q.right)


def isSameTreeV3(p, q):
    if not p and not q: return True
    if not p or not q: return False

    s1, s2 = [p], [q]
    while s1 and s2:
        node1, node2 = s1.pop(), s2.pop()
        if node1 and node2:
            if node1.val != node2.val:
                return False
            s1.append(node1.right)
            s1.append(node1.left)
            s2.append(node2.right)
            s2.append(node2.left)
        elif node1 or node2:
            return False
    return True

scala

import scala.collection.mutable.Stack

object LC100 {
  def isSameTree(p: TreeNode, q: TreeNode): Boolean =
    (p, q) match {
      case (null , null) => true
      case (_, null) | (null, _) => false
      case _ => p.value == q.value & isSameTree(p.left, q.left) & isSameTree(p.right, q.right)
    }

  def isSameTreeV2(p: TreeNode, q: TreeNode): Boolean = {
    if (p == null & q == null) return true
    if (p == null | q == null) return false

    val (s1, s2) = (Stack(p), Stack(q))

    while (s1.nonEmpty & s2.nonEmpty) {
      val (node1, node2) = (s1.pop(), s2.pop())
      if (node1 != null & node2 != null) {
        if (node1.value != node2.value) return false
        s1.push(node1.right)
        s1.push(node1.left)
        s2.push(node2.right)
        s2.push(node2.left)
      } else if (node1 != null | node2 != null )
        return false
    }
    true
  }
}

最后

欢迎交流和补充