[数据结构与算法]Leetcode-101. 对称二叉树

链接

101. 对称二叉树

题目

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

示例

示例 1：

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

示例 2：

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

思路

一开始想，通过中序遍历得到所有节点的值，中序遍历后的值是对称的就行，比如，示例1的中序遍历结果是3 2 4 1 4 2 3，将结果保存到数组当中，再判断数组中的值是否对称。

如下所示：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    void traversal(TreeNode* root){
        if(root==nullptr) return;
        traversal(root->left);
        res.push_back(root->val);
        traversal(root->right);

    }
    bool isSymmetric(TreeNode* root) {
        //中序遍历后 对称
        traversal(root);
        int n=res.size();
        for(int i=0;i<n/2;i++)
        {
            if(res[i]!=res[n-i-1]) return false;
        }
        return true;
    }
};

然而，有bug。

因此，换个思路，通过双指针遍历这棵树，p指针和?q指针都指向root，随后?p?右移时，q?左移，p?左移时，q?右移，检查p?和?q?节点的值是否相等。

C++ Code?

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};