- 题目描述
- 思路与解答
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像
代码语言：javascript复制源二叉树 8
/
6 10
/ /
5 7 9 11
镜像二叉树
8
/
10 6
/ /
11 9 7 5
思路与解答
使用递归，直接将左子树反转，右子树反转，交换即可。值得注意的是，反转后的结果需要先保存，左右两个都反转之后，才能赋值。
代码语言：javascript复制/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public static void Mirror(TreeNode root) {
if (root == null) {
return;
} else {
root = reverse(root);
}
}
public static TreeNode reverse(TreeNode root) {
if (root == null) {
return root;
} else {
TreeNode left = reverse(root.right);
TreeNode right = reverse(root.left);
root.left = left;
root.right =right;
return root;
}
}
那这道题如果不用递归怎么做？
其实我们可以使用栈来完成，先把根节点压进栈，循环判断栈是否为空，不为空则取出第一个元素，交换左右节点，然后将左右节点只要不为null，压进栈即可，循环直到栈为空。
show you the code!!!
代码语言：javascript复制 public static void Mirror(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
TreeNode tempNode = node.left;
node.left = node.right;
node.right = tempNode;
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
}
此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~
技术之路不在一时，山高水长，纵使缓慢，驰而不息。
