27_226. 翻转二叉树
题目描述：
解题思路：
- 递归：
- 自底向上：如果当前遍历的节点
root的左右两颗子树都已经翻转了，那么只需要交换两棵子树的位置即可- 自顶向下：交换当前节点的左右节点，递归的交换当前节点的左右子树
- 迭代：将根节点入队，交换根节点的左右子树，然后左右子树入队列，交换左右子树的左右子树，迭代下去即可
代码：
自底向上
//自底向上：
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
自顶向下
//自顶向下：
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
迭代
//迭代：
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode left = node.left;
node.left = node.right;
node.right = left;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}