基本思想

首先要明确，题目所定义的 “对称” 是对每层而言，同时考虑空节点。

因此，如果我们使用常规的遍历方式进行检查的话，需要对空节点有所表示。

局部检查（层序遍历）

我们使用 0x3f3f3f3f 作为无效值，并建立占位节点 emptyNode 用来代指空节点（emptyNode.val = 0x3f3f3f3f）。

一个朴素的做法是：使用「层序遍历」的方式进行「逐层检查」，对于空节点使用 emptyNode 进行代指，同时确保不递归 emptyNode 对应的子节点。

具体做法如下：

  1. 起始时，将 root 节点入队；

  2. 从队列中取出节点，检查节点是否为 emptyNode 节点来决定是否继续入队：

    • 当不是 emptyNode 节点时，将其左/右儿子进行入队，如果没有左/右儿子，则用 emptyNode 代替入队；
    • 当是 emptyNode 节点时，则忽略

  3. 在进行流程 22 的同时使用「临时列表」记录当前层的信息，并检查当前层是否符合 “对称” 要求；

  4. 循环流程 22 和 33，直到整个队列为空。

代码： 
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if pRoot == None:
            return True
        INF = 0x3f3f3f3f
        emptyNode = TreeNode(INF)
        queue = []
        queue.append(pRoot)

        while queue:
            size = len(queue)
            list = []
            while size:
                size -=1
                node = queue.pop(0)
                if not node == emptyNode:
                    queue.append(node.left if node.left !=None else emptyNode)
                    queue.append(node.right if node.right !=None else emptyNode)
                list.append(node.val)  
            if not self.check(list): return False
        return True
    def check(self,list):
        l = 0
        r = len(list)-1
        while l <r:
            if not list[l] ==list[r]:
                return False
            l+=1
            r-=1
        return True
  • 时间复杂度：在层序遍历过程中，每个节点最多入队一次，同时在 check 检查对称性过程中，每层只会被检查一次。复杂度为 O(n)
  • 空间复杂度：O(n)

整体检查（递归）

在「层序遍历」解法中，我们利用了 “对称” 定义对每层进行检查。

本质上这是利用 “对称” 定义进行多次「局部」检查。

事实上，我们还可以利用 “对称” 定义在「全局」层面上进行检查。

我们如何定义两棵子树 a 和 b 是否 “对称” ？

当且仅当两棵子树符合如下要求时，满足 “对称” 要求：

  1. 两棵子树根节点值相同；
  2. 两颗子树的左右子树分别对称，包括：
    • a 树的左子树与 b 树的右子树相应位置的值相等
    • a 树的右子树与 b 树的左子树相应位置的值相等

具体的，我们可以设计一个递归函数 check ，传入待检测的两颗子树的头结点 a 和 b（对于本题都传入 root 即可），在单次查询中有如下显而易见的判断子树是否 “对称” 的 Base Case：

  • a 和 b 均为空节点：符合 “对称” 要求；
  • a 和 b 其中一个节点为空，不符合 “对称” 要求；
  • a 和 b 值不相等，不符合 “对称” 要求；

其他情况，我们则要分别检查 a 和 b 的左右节点是否 “对称” ，即递归调用 check(a.left, b.right) 和 check(a.right, b.left)。

代码： 

class Solution:
    def isSame(self,root1, root2):
        if not root1 and not root2:return True
        if not root1&nbs***bsp;not root2:return False
        return root1.val == root2.val and self.isSame(root1.left, root2.right)\
    and self.isSame(root1.right, root2.left)
    def isSymmetrical(self, pRoot):
        # write code here
        return self.isSame(pRoot,pRoot)
  • 时间复杂度：每个节点只会被访问一次。复杂度为 O(n)
  • 空间复杂度：O(n)

总结

上述两种解法不仅仅是实现上的不同，更多的是检查 “出发点” 的不同：

  • 解法一：利用「层序遍历」的方式，以 “层” 为单位进行 “对称” 检查；
  • 解法二：利用「递归树展开」的方式，以 “子树” 为单位进行 “对称” 检查。

当我们从整体层面出发考虑时，配合递归，往往能写出比常规做法要简洁得多的代码。

建议大家加深对「局部」和「整体」两种不同出发点的理解。


参考资料：