Invert Binary Tree

Posted on Edited on In Views:

226.Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

img

1
2
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

img

1
2
Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

1
2
Input: root = []
Output: []

递归法：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void tree_next(TreeNode* root) {
        if(!root)return;
        tree_next(root->left);
        tree_next(root->right);
        TreeNode* temp;
        temp = root->right;
        root->right = root->left;
        root->left = temp;
    }
    TreeNode* invertTree(TreeNode* root) {
        tree_next(root);
        return root;
    }
};

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    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;
    }
};