226. 翻转二叉树
一句话套路递归交换左右孩子
题目描述
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
示例 1:

输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1]
示例 2:

输入:root = [2,1,3] 输出:[2,3,1]
示例 3:
输入:root = [] 输出:[]
提示:
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
思路
时间
O(n)空间
O(h)思路
每个结点交换左右孩子,递归下去。前序或后序都行(不像 Q101 需要成对比较)。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)C++17 题解
namespace lc0226 {
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
std::swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0226::Solution s;
TreeNode* a = buildTree({4, 2, 7, 1, 3, 6, 9});
TreeNode* inv = s.invertTree(a);
CHECK_EQ(treeToVec(inv), OptVec{4, 7, 2, 9, 6, 3, 1});
freeTree(inv);
TreeNode* b = buildTree({2, 1, 3});
CHECK_EQ(treeToVec(s.invertTree(b)), OptVec{2, 3, 1});
freeTree(b);