101. Symmetric Tree

判断一棵树是否是镜面对称的。最好同时提供递归和迭代的解法

思路：非常巧妙，helper接受的两个参数起初都是root,但是会递归的比较它们的左右子树

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # 6 star, 必须掌握
        return self.helper(root, root)
    def helper(self, node1, node2):
        if not node1 and not node2:  # 都是None
            return True
        if not node1 or not node2:
            return False
        if node1.val != node2.val:
            return False
        return self.helper(node1.left, node2.right) and self.helper(node1.right, node2.left)

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 6 star, 没想出来，必须熟练掌握
func isSymmetric(root *TreeNode) bool {
	return helper(root, root)

}

func helper(node1 *TreeNode, node2 *TreeNode) bool {
	 if node1 == nil && node2 == nil {return true}
	 if (node1 == nil && node2 != nil) || (node1 != nil && node2 == nil) {
	 	return false
	 }
	 if node1.Val != node2.Val {return false}
	 return helper(node1.Left, node2.Right) && helper(node1.Right, node2.Left)
}