最近找实习问到的题目。。
属于是简单题中的典中典题目了。
整理一下加深印象。。。
题目
给一颗二叉树，输出他的镜像。
例如：
输入：
1
2
3
4
5
| 1
/ \
2 3
/ \ / \
4 5 6 7
|
输出
1
2
3
4
5
| 1
/ \
3 2
/ \ / \
7 6 5 4
|
思路
交换输出二叉树的镜像，实际上就是交换每一个二叉树的左右子树。
最先想到使用栈来保存二叉树的根节点，交换其子树。
代码
使用栈的迭代法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public TreeNode MirrorTree(TreeNode root){
if(root==null) return null;
Stack<TreeNode> stack =new Stack<>();
stack.add(root);
while(!stack.isEmpty()){
TreeNode root =stack.pop();
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
if(root.left!=null){
stack.push(root.left);
}
if(root.right!=null){
stack.push(root.right);
}
}
return root;
}
|
递归法。实际上也是栈。。。递归栈
1
2
3
4
5
6
7
8
| public TreeNode MirrorTree(TreeNode root){
if(root==null) return null;
TreeNode r=MirrorTree(root.left);
TreeNode l=MirrorTree(root.right);
root.left=l;
root.right=r;
return root;
}
|
延伸
回头来看，无论是递归法还是迭代法，其实这道题的解法，不过就是在二叉树的后续遍历模板上多加了一个交换左右子树的功能。
因此立即推==>牢固掌握基础的二叉树操作( 二叉树的DFS和BFS遍历 )的重要性。