226. 翻转二叉树

问题描述

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

法一、递归

单独递归函数，返回TreeNode* x，x是从当前层开始的逆转后的树的根结点

class Solution {
public:
    TreeNode* solve(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* t = root->left;
        root->left = solve(root->right);
        root->right = solve(t);
        return root;
    }
    TreeNode* invertTree(TreeNode* root) {
        TreeNode* res = solve(root);
        return res;        
    }
};

法二、队列

同二叉树的最大深度那题，可以使用队列配合for循环，对每个层的结点依次处理，交换其左右子树。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> q;
        if(root == nullptr) {
            return nullptr;
        }
        q.push(root);
        while(!q.empty()) {
            int layer_size = q.size();
            for (int i = 0; i < layer_size; i++) {
                TreeNode* t = q.front();
                q.pop();
                // swap
                TreeNode* tmp = t->left;
                t->left = t->right;
                t->right = tmp;
                // push queue
                if (t->left != nullptr) {
                    q.push(t->left);
                }
                if (t->right != nullptr) {
                    q.push(t->right);
                }
            }
        }
        return root;
    }
};