226.翻转二叉树
- 题目:
1 | 翻转一棵二叉树。 |
- 思路:翻转二叉树即为镜像左子树和右子树,逐节点交换左右两节点的指针即可。
迭代:
使用前序遍历,交换所有左右子节点。
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return root;
auto rt = root;
stack<TreeNode*> st;
while(!st.empty() || root){
if(root){
swap(root->left, root->right);
st.push(root->right);
root = root->left;
}
else{
root = st.top();
st.pop();
}
}
return rt;
}
};时间复杂度:
O(N)
,空间复杂度O(N)
递归:
- 如上所述,翻转二叉树需要对每个节点交换其左右节点,需要遍历二叉树,并交换左右节点;
- 终止条件:节点为空;
- 递推公式:DFS或BFS
NOTE:不能使用中序遍历,如果在先遍历左侧节点,中间交换了左右节点位置,访问右侧节点时会发生错误。
前序遍历代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return root;
preorderTrversal(root);
return root;
}
private:
void preorderTrversal(TreeNode* root){
if(!root) return;
swap(root->left, root->right);
preorderTrversal(root->left);
preorderTrversal(root->right);
}
};后序遍历也是一样。时间复杂度
O(N)
,空间复杂度O(N)
。