# 题目
你一棵二叉树的根节点 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]
226. 翻转二叉树 - 力扣(LeetCode)
# 分析
翻转二叉树其实就是把每个节点的左右孩子互换即可
递归法:
class Solution { | |
public: | |
TreeNode* invertTree(TreeNode* root) { | |
if (root == NULL) return root; | |
swap(root->left, root->right); // 中 | |
invertTree(root->left); // 左 | |
invertTree(root->right); // 右 | |
return root; | |
} | |
}; |
迭代法:
前序遍历
class Solution { | |
public: | |
TreeNode* invertTree(TreeNode* root) { | |
stack<TreeNode*> st; | |
if (root != NULL) st.push(root); | |
while (!st.empty()) { | |
TreeNode* node = st.top(); | |
if (node != NULL) { | |
st.pop(); | |
if (node->right) st.push(node->right); // 右 | |
if (node->left) st.push(node->left); // 左 | |
st.push(node); // 中 | |
st.push(NULL); | |
} else { | |
st.pop(); | |
node = st.top(); | |
st.pop(); | |
swap(node->left, node->right); // 节点处理逻辑 | |
} | |
} | |
return root; | |
} | |
}; |
层序遍历
class Solution { | |
public: | |
TreeNode* invertTree(TreeNode* root) { | |
queue<TreeNode*> que; | |
if (root != NULL) que.push(root); | |
while (!que.empty()) { | |
int size = que.size(); | |
for (int i = 0; i < size; i++) { | |
TreeNode* node = que.front(); | |
que.pop(); | |
swap(node->left, node->right); // 节点处理 | |
if (node->left) que.push(node->left); | |
if (node->right) que.push(node->right); | |
} | |
} | |
return root; | |
} | |
}; |