不懂一点数据结构。
读题
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
据图示，应该是完全对称的左右翻转。
有节点定义：
1
2
3
4
5
6
7
8
9
|
struct TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {}
};
|
思路
考虑使用递归；先左后右。
1
2
3
4
5
6
7
| void fun(root){
if root==nullptr return;
do fun(root->left);
do fun(root->right);
switch(root->left, root->right);
return;
}
|
写成 cpp 就是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
void fun(TreeNode* root){
if(root==nullptr) return;
fun(root->left);
fun(root->right);
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
return;
}
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr) return root;
fun(root);
return root;
}
};
|
结果
一次通过，执行时间 0 ms（啊？），消耗内存 12.17 MB。
就像题解评论说的，”幸福来得太突然”，我自己还没反应过来，就过了。
收获
递归确实非常擅长处理树和链表这种单向的逻辑的数据结构。