leetcode101：对称二叉树

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

// 二叉树结点的定义
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) {}
};

const int NULL_NODE = 0;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    递归实现

    时间复杂度：O(n)
        其中 n 为二叉树结点的个数，从上到下每个结点被遍历一次。
    空间复杂度：O(n)
        递归使用的栈空间有关，递归层数不超过 n。
*/
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }

        return dfs(root, root);
    }

    bool dfs(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        }
        if (p == nullptr || q == nullptr || p->val != q->val) {
            return false;
        }

        return dfs(p->left, q->right) 
            && dfs(p->right, q->left);
    }
};

/*
    迭代实现，层序遍历
    
    时间复杂度：O(n)
    空间复杂度：O(n)
        使用一个队列来维护结点，每个结点最多进队一次，出队一次。
        队列中最多不会超过 n 个点，空间复杂度为 O(n)。
*/
class Solution_1 {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }

        queue<TreeNode*> que;
        que.push(root->left);
        que.push(root->right);

        while (!que.empty()) {
            TreeNode* p = que.front(); que.pop();
            TreeNode* q = que.front(); que.pop();
            // 结点为空时，下一轮退出
            if (p == nullptr && q == nullptr) {
                continue;
            }
            if (p == nullptr || q == nullptr || p->val != q->val) {
                return false;
            }
            
            que.push(p->left); que.push(q->right);
            que.push(p->right); que.push(q->left);
        }

        return true;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> root_cases = {
        {1,2,2,3,4,4,3},
        {1,2,2,NULL_NODE,3,NULL_NODE,3}
    };

    for (const auto& nums : root_cases) {
        cout << "Input: ";
        printArray(nums);

        // 创建二叉树
        TreeNode* root = createTree(nums);
        // 中序遍历
        bool result = solution.isSymmetric(root);
        cout << "Output: " << (result ? "true" : "false") << endl;
        
        // 释放内存
        deleteTree(root);
    }

    return 0;
}