226. 翻转二叉树

1.题目描述

翻转一棵二叉树。
示例：
输入：

输出：

2.方法1（递归）

翻转一颗空树还是空树，因此，对于每一个节点，分别翻转它的子树，把该节点的左右子树交换，递归的翻转所有节点。

3.代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL){
            return NULL;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

4.复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

5.方法2（迭代）

利用队列，
（1）把根节点放入队列中。
（2）交换根节点的左右子节点，如果左右子节点不为空，则入队。
（3）把队列头部的节点出队，交换左右子节点，如果该节点的左右子节点不为空，则入队。
（4）重复（3）直到队列为空。

6.代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL){
            return NULL;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            swap(node->left,node->right);
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
        return root;
    }
};

7.复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)