Symmetric Tree

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

題意

判斷是否對稱二叉樹（以根節(jié)點為中垂線鏡像對稱，包括結(jié)構(gòu)和節(jié)點值）。

分析

轉(zhuǎn)換思路：先判斷兩顆樹是否相同（結(jié)構(gòu)+節(jié)點值），再判斷根節(jié)點的左子樹和右子樹是否相同即可；

這里只寫出最簡寫法，更多寫法參考相同的樹。

代碼

python

def isSymmetric(root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    def dfs(p, q):
        if not p and not q: return True
        if not p or not q: return False
        left_same = dfs(p.left, q.right)
        right_same = dfs(p.right, q.left)
        return p.val == q.val and left_same and right_same
    return dfs(root.left, root.right) if root else True

scala

object LC101 {
  def isSymmetric(root: TreeNode): Boolean = {
    def dfs(p: TreeNode, q: TreeNode): Boolean = (p, q) match {
      case (null, null) => true
      case (null, _) | (_, null) => false
      case _ => p.value == q.value & dfs(p.left, q.right) & dfs(p.right, q.left)
    }
    if (root == null) true else dfs(root.left, root.right)
  }
}

最后

歡迎交流和補(bǔ)充