LeetCode 101.对称二叉树 python/scala

Symmetric Tree

环境：python 3.6，scala 2.11.8

题意

判断是否对称二叉树（以根节点为中垂线镜像对称，包括结构和节点值）。

分析

转换思路：先判断两颗树是否相同（结构+节点值），再判断根节点的左子树和右子树是否相同即可；

这里只写出最简写法，更多写法参考相同的树。

代码

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

最后

欢迎交流和补充