Leetcode 第101题：Symmetric Tree--对称二叉树（C++、Python）

题目地址：Symmetric Tree

---

题目简介：

给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

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

但是[1,2,2,null,3,null,3]就不是:

    1
   / \
  2   2
   \   \
   3    3

---

题目解析：

1、递归

在进行对比时，有两种直接的想法。一种是一行行的进行对比，另一种就是从外向内，逐个对应位置的进行分析。深度搜索便是上面的从外往内，如例1所示可以先一次验证外面的[1, 2, 3]，然后对比[4]。

C++：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root)
            return true;
        return helper(root -> left, root -> right);
    }
    bool helper(TreeNode* left, TreeNode* right)
    {
        if (!left && ! right)
            return true;
        if ((!left && right) || (left && !right) || (left -> val != right -> val))
            return false;
        return (helper(left -> left, right -> right) && helper(right -> left, left -> right));
    }
};

Python版：

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root== None:
            return True
        return self.helper(root.right, root.left)
    def helper (self, left, right):
        if left == None and right == None:
            return True
        if ((not left and right) or (left and not right) or (left.val != right.val)):
            return False
        return self.helper(left.left, right.right) and self.helper(right.left, left.right)