Leetcode：101. 对称二叉树（C++）_leetcode 101 c++

目录

问题描述：

实现代码：

基于中序遍历（错误方法）：

递归：

---

问题描述：

        给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

实现代码：

基于中序遍历（错误方法）：

class Solution {
public:
    //中序遍历
    void traversal(TreeNode* cur,vector<int>& v)
    {
        if(cur==NULL)
        {
            return;
        }
        traversal(cur->left,v);
        v.push_back(cur->val);
        traversal(cur->right,v);                
    }
    bool isSymmetric(TreeNode* root) 
    {
        vector<int> v;
        traversal(root,v);
        int i=0;
        int j=v.size()-1;
        //判断数组是否对此即可
        while(i<j)
        {
            if(v[i]!=v[j])
            {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
};

        此方法就是中序遍历，然后判断结果是对称，看起来很有道理是吧，事实上，确实可以应付绝大部分情况。

        但有某些特定情况就无法给出正确的结果了，例如：[1，2，2，2，null，2]这个二叉树，写出中序遍历[2，2，1，2，2]，你会发现它也是对称的，但它却不是一个对称二叉树，所以此方法还需改进，这里我们继续介绍别的方法。

递归：

class Solution {
public:
    //比较左右子树
    bool compare(TreeNode* left,TreeNode* right)
    {
        if(left!=NULL&&right==NULL) return false;//左子树不为空，右子树为空
        else if(left==NULL&&right!=NULL) return false;//左子树为空，右子树不为空
        else if(left==NULL&&right==NULL) return true;//左右子树都为空
        else if(left->val!=right->val) return false;//左右子树数值不同
        bool outside=compare(left->left,right->right);//比较外侧 
        bool inside=compare(left->right,right->left);//比较内侧  
        return outside&&inside;                               
    }
    bool isSymmetric(TreeNode* root) 
    {
      if(root==NULL) return true;
      bool result=compare(root->left,root->right);
      return result; 
    }
};

原理思路：

        这种方法相当于后序遍历的思路，因为我们要知道左右子树是否相等来向上一层返回，显然后序是符合这种要求的。