leetcode.101.Symmetric Tree

Description

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1 / \ 2 2 / \ / \ 3 4 4 3

But the following [1,2,2,null,3,null,3] is not:

1 / \ 2 2 \ \ 3 3

sln1

通过深度优先搜索去遍历一棵树，有三种可选的顺序，分别是前序，中序和后序。这里的前中后是指要在什么时候算上父节点，是遍历子节点前，还是两个节点之间还是遍历完子节点之后？在这里我们随便选择一种遍历顺序，我选择了后序遍历。在后续遍历中，如果我对每个节点都是先遍历左子节点的话，最终会得到一种树节点的列表顺序。而如果我先遍历右子节点的话，又会得到一种树节点的列表顺序。如果这两个顺序是相等的，说明这个树是对称的。实现代码如下：

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ return root is None or (self.leftFirst(root) == self.rightFirst(root)) def leftFirst(self, root): if root is None: return [None] nodes = [] nodes.extend(self.leftFirst(root.left)) nodes.extend(self.leftFirst(root.right)) nodes.append(root.val) return nodes def rightFirst(self, root): if root is None: return [None] nodes = [] nodes.extend(self.rightFirst(root.right)) nodes.extend(self.rightFirst(root.left)) nodes.append(root.val) return nodes

sln2

在sln1的提交结果分析中，发现这种深度优先搜索的方法仅仅超过了10%+的python结果，说明还有很大的优化空间。不难发现，在sln1中，如果树是不对称的，我们还是会把整棵树遍历完之后才会发现，而且是遍历两遍。但如果一颗不对称的树很深，而且在靠近叶子节点的地方就出现不对称的情况了，这样我们其实是能够更早就发现的。所以我们要想一种方法，能够实现当树一旦出现不对称的情况，我们就不再做无效的计算。 通过参考Discuss中大牛们的解法，看到一种十分易于理解且高效的实现，思路如下：如果一棵树是对称的，那么他的左子树和右子树应该互为镜像。那么怎么判断左子树和右子树互为镜像呢，首先是左子树和右子树的根节点要相等。其次是左子树的左子树要和右子树的右子树互为镜像（isMirror(root.left.left, root.right.right)）同时左子树的右子树和右子树的左子树要互为镜像（isMirror(root.left.right, root.right.left)）。那么，一旦某个子节点不是对称的，他就会返回给上面的父节点。上面的父节点知道下面已经有不对称的子树了，自己已经不可能对称了，就会不断把这个消息上传，至到树的根节点。所以避免掉了许多无效的操作。利用这种算法，我们成功超过了95%+的python程序。算法实现如下：

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ return root is None or self.isMirror(root.left, root.right) def isMirror(self, nodeA, nodeB): if nodeA is None and nodeB is None: return True if nodeA is None or nodeB is None: return False return (nodeA.val == nodeB.val) and self.isMirror(nodeA.left, nodeB.right) and self.isMirror(nodeA.right, nodeB.left)