leetcode226：翻转二叉树

题目链接

leetcode

题目描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
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 = -101;

// 辅助函数：创建二叉树
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)
        由递归栈的深度决定，它等于当前结点在二叉树中的高度。
        在平均情况下，二叉树的高度与结点个数为对数关系，即 O(logN)。
        在最坏情况下，二叉树形成链状，空间复杂度为 O(N)。
*/
// 思路：遍历
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        dfs(root);
        return root;
    }

    void dfs(TreeNode* root) {
        if (root == nullptr) {
            return;
        }

        // 该结点交换左右子结点
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;

        // 遍历左右子树的结点
        dfs(root->left);
        dfs(root->right);
    }
};
// 思路：分解问题
class Solution_1 {
public:
    // 函数定义：以 root 为根结点的二叉树翻转，返回翻转后二叉树的根结点
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        // 根据函数定义，递归地翻转左右子树
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        // 交换左右子结点
        root->left = right;
        root->right = left;

        return root;
    }
};

/*
    迭代实现

    时间复杂度：O(N)
    空间复杂度：O(N)
*/
class Solution_2 {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        stack<TreeNode*> stk;
        stk.push(root);

        while (!stk.empty()) {
            TreeNode* node = stk.top(); stk.pop();
            // 该结点交换左右子结点
            TreeNode* temp = node->left;
            node->left = node->right;
            node->right = temp;

            // 遍历左右子树的结点
            if (node->left != nullptr) {
                stk.push(node->left);
            }
            if (node->right != nullptr) {
                stk.push(node->right);
            }
        }

        return root;
    }
};

// 辅助函数：打印数组
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;
}

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

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

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

        // 创建二叉树
        TreeNode* root = createTree(nums);
        // 翻转二叉树
        root = solution.invertTree(root);
        cout << "Output: ";
        levelOrderTraversal(root);

        // 释放内存
        deleteTree(root);
    }

    return 0;
}