镜像二叉树
题意
操作给定的二叉树，将其变换为源二叉树的镜像。
样例
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5思路
递归法
- 递归的终止条件就是当前树为
null或该树的左子树与右子树都为null。 - 递归操作是交换当前数的左右子树。
- 递归条件：
- 当前数的左子树不为空时对左字树进行递归操作。
- 当前数的右子树不为空时对右子树进行递归操作。
模拟压栈法
既然递归的原理是通过压栈实现的，那么我们也可以自己来创建一个栈来模拟实现。
先将根节点放入栈中，然后开始循环，循环条件是栈不为空，将栈顶元素出栈，当该节点的左子树或右子树不为空，就将左右子树进行交换，然后当左子树不为空时，将左子树压栈，当右子树不为空时，将右子树压栈。如此循环，直到栈为空。
代码实现
递归法
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
if (root.left != null)
Mirror(root.left);
if (root.right != null)
Mirror(root.right);
}
}模拟压栈法
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.Stack;
public class Solution {
//模拟递归的压栈法
public void Mirror(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
if (node.left != null || node.right != null) {
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
}
}原题地址
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-08-232，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录