翻转二叉树

比起调用层序遍历，递归竟然更快

难道数据结构的调用与操作时间开销很大？

226.翻转二叉树

力扣题目链接(opens new window)

翻转一棵二叉树。

这道题目背后有一个让程序员心酸的故事，听说 Homebrew的作者Max Howell，就是因为没在白板上写出翻转二叉树，最后被Google拒绝了。（真假不做判断，权当一个乐子哈）

//
// Created by 徐昊岩 on 2024/2/15.
//
#include "bits/stdc++.h"

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) {}
};

class Solution {
public:
    TreeNode *invertTree(TreeNode *root) {
        queue<TreeNode *> q;
        if (root!= nullptr) q.emplace(root);  //if(root)还是if(!root)要注意
        while (!q.empty()) {
            int size = q.size();
            for(int i=0;i<size;i++){
                TreeNode *temp=q.front();
                q.pop();
                if(temp->right== nullptr&&temp->left== nullptr) continue;
                else{
                    TreeNode *t=temp->right;
                    temp->right=temp->left;
                    temp->left=t;
                }
                if(temp->right!= nullptr) q.emplace(temp->right);
                if(temp->left!= nullptr) q.emplace(temp->left);
            }
        }
        return root;
    }
};
class Solution2{
public:
    TreeNode *invertTree(TreeNode *root){
        if(!root) return root;
        if(root->right== nullptr&&root->left== nullptr) return root;
        else{
            TreeNode *temp=root;
            TreeNode *t=temp->right;
            temp->right=temp->left;
            temp->left=t;
            if(temp->left!= nullptr) invertTree(temp->left);
            if(temp->right!= nullptr) invertTree(temp->right);
            return root;
        }
    }
};