Same Tree

環(huán)境：python 3.6，scala 2.11.8

題意

判斷兩顆二叉樹(shù)是否相同（結(jié)構(gòu)相同 + 各節(jié)點(diǎn)值相同）。

分析

首先，題意非常明確：當(dāng)兩顆樹(shù)結(jié)構(gòu)相同、各節(jié)點(diǎn)值相同時(shí)，則稱這兩棵樹(shù)相同。因此，用集合裝載節(jié)點(diǎn)值、判斷集合中元素值是否相同無(wú)法通過(guò)，它無(wú)法判斷結(jié)構(gòu)是否相同。

• 基礎(chǔ)：掌握樹(shù)的先序、中序、后序三種遍歷方式（DFS/BFS 方法）；

• 選定上述一種遍歷方式后，可在遍歷過(guò)程中判斷：

  • 兩顆樹(shù)只有其中一顆樹(shù)有子節(jié)點(diǎn)，則說(shuō)明兩樹(shù)不同；

  • 兩個(gè)樹(shù)都有子節(jié)點(diǎn)：

    • 節(jié)點(diǎn)值不同，則說(shuō)明兩樹(shù)不同；

    • 節(jié)點(diǎn)值相同，繼續(xù)遍歷；

代碼

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
  }
}

最后

歡迎交流和補(bǔ)充