题目描述

题目链接：226. Invert Binary Tree

Invert a binary tree.

例子

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

解题思路

利用递归方法求解，首先当 root == nullptr 时直接返回 root。否则完成以下步骤：

• invert(root->left), invert(root->right)
• swap(root->left, root->right)

代码如下：

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

• 时间复杂度: O(n)
• 空间复杂度: O(h)

GitHub 代码同步地址： 226.InvertBinaryTree.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions