对称二叉树

原题：

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

  1.     1
  2.    / \
  3.   2   2
  4.  / \ / \
  5. 3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

解题方法：

解法一（用两个vector存储，分别递归遍历左右两个子树，O(n)复杂度）：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        bool is=true;
        vector<int> left(0);
        vector<int> right(0);
        LeftTest(root->left,left);
        RightTest(root->right,right);
        if(left.size()!=right.size())
            return false;
        for(int i=0;i<left.size();i++)
        {
            if(left[i]!=right[i])
                return false;      
        }
        return is;
    }

    void LeftTest(TreeNode* side,vector<int> &a)
    {
        if(!side)
        {
            a.push_back(-1);
            return;
        }  //注意这里push -1很有必要，是为了避免值相同但不对称的情况
        a.push_back(side->val);
        LeftTest(side->left,a);
        LeftTest(side->right,a);
    }

    void RightTest(TreeNode* side,vector<int> &a)
    {
        if(!side) 
        {
            a.push_back(-1);
            return;
        }
        a.push_back(side->val);
        RightTest(side->right,a);
        RightTest(side->left,a);
    }
};

解法二（同样使用递归，但不适用向量）：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return SymTest(root->left,root->right);
    }

    bool SymTest(TreeNode* left,TreeNode* right)
    {
        if(left==NULL&&right==NULL)
            return true;
        if(left==NULL||right==NULL)
            return false;
        return (left->val==right->val)&&SymTest(left->left,right->right)&&SymTest(left->right,right->left);
    }
};

做题小结：

针对解法一：

  1. 使用向量来存储，避免使用数组时必须一开始就声明大小。

针对解法二：

  1. 直接新创建一个函数，左子树的左子树对应右子树的右子树，左子树的右子树对应右子树的左子树，极大地节省了空间
  2. 在最后的return环节还是没有靠自己写出来，需要再仔细研究一下