HOT100-5-翻转二叉树

题目描述

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

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

具体见题目描述。

算法思路

​ 这个第一眼就很容易想到使用递归+DFS， 一直搜到最下面的叶子结点，然后对于第 n-1层，交换第 n层的两个节点即可。代码如下：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return nullptr;
        }
        if (root->left) {
            invertTree(root->left);
        }
        if (root->right) {
            invertTree(root->right);
        }
        swap(root->left, root->right);
        return root;
    }
};

效率是 O(n)，空间复杂度占用比较高，但是我甚至没有声明中间变量，猜测是 swap函数的问题，我们修改一下swap函数手动实现发现还是不行，下面这份题解在官方显示消耗内存最低，但是我这里并不行，很奇怪：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return root;
        TreeNode* temp;
        temp=root->left;
        root->left=root->right;
        root->right=temp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};