翻转二叉树
问题
这个题目说的是,给你一棵二叉树,你要把它左右镜像翻转,然后返回翻转后的二叉树。
比如说,给你的二叉树是:
1
/
2 4
/
8 16
左右翻转后的二叉树是:
1
/
4 2
/
16 8
我们可以看到,二叉树上所有节点都沿中轴线左右互换了位置
代码
public class AlgoCasts {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public TreeNode invertBinaryTreeRecursive(TreeNode root) {
if (root == null) return root;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertBinaryTreeRecursive(root.left);
invertBinaryTreeRecursive(root.right);
return root;
}
public TreeNode invertBinaryTreeIterative(TreeNode root) {
if (root == null) return root;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
return root;
}
}
近期评论