0%

[Leetcode]226. Invert Binary Tree(C++)

题目描述

题目链接: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)

代码如下:

1
2
3
4
5
6
7
8
9
10
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