1，BFS解决
之前讲373，数据结构-6,树的时候，提到过二叉树的广度优先搜索，就是一层一层的访问，像下面这样
二叉树的BFS代码如下
public static void treeBFS(TreeNode root) {
//如果为空直接返回
if (root == null)
return;
//队列
Queue<treenode> queue = new LinkedList<>();
//首先把根节点加入到队列中
queue.add(root);
//如果队列不为空就继续循环
while (!queue.isEmpty()) {
//poll方法相当于移除队列头部的元素
TreeNode node = queue.poll();
//打印当前节点
System.out.println(node.val);
//如果当前节点的左子树不为空，就把左子树
//节点加入到队列中
if (node.left != null)
queue.add(node.left);
//如果当前节点的右子树不为空，就把右子树
//节点加入到队列中
if (node.right != null)
queue.add(node.right);
}
}
这题要求的是输出二叉树的镜像，就是每一个节点的左右子节点进行交换，随便画个二叉树看一下
我们需要遍历每一个节点，然后交换他的两个子节点，一直循环下去，直到所有的节点都遍历完为止，代码如下
public TreeNode Mirror(TreeNode root) {
//如果为空直接返回
if (root == null)
return null;
//队列
final Queue<treenode> queue = new LinkedList<>();
//首先把根节点加入到队列中
queue.add(root);
while (!queue.isEmpty()) {
//poll方法相当于移除队列头部的元素
TreeNode node = queue.poll();
//交换node节点的两个子节点
TreeNode left = node.left;
node.left = node.right;
node.right = left;
//如果当前节点的左子树不为空，就把左子树
//节点加入到队列中
if (node.left != null) {
queue.add(node.left);
}
//如果当前节点的右子树不为空，就把右子树
//节点加入到队列中
if (node.right != null) {
queue.add(node.right);
}
}
return root;
}
2，DFS解决
无论是BFS还是DFS都会访问到每一个节点，访问每个节点的时候交换他的左右子节点，直到所有的节点都访问完为止，代码如下
public TreeNode Mirror(TreeNode root) {//DFS
//如果为空直接返回
if (root == null)
return null;
//栈
Stack<treenode> stack = new Stack<>();
//根节点压栈
stack.push(root);
//如果栈不为空就继续循环
while (!stack.empty()) {
//出栈
TreeNode node = stack.pop();
//子节点交换
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);
}
return root;
}
3，中序遍历解决
这题其实解法比较多，只要访问他的每一个节点，然后交换子节点即可，我们知道二叉树不光有BFS和DFS访问顺序，而且还有前序遍历，中序遍历和后续遍历等，不管哪种访问方式，只要能把所有节点都能访问一遍然后交换子节点就能解决，我们这里就以中序遍历来看下，前序和后序就不在看了。在373，数据结构-6,树中，提到二叉树中序遍历的非递归写法如下
public static void inOrderTraversal(TreeNode tree) {
Stack<treenode> stack = new Stack<>();
while (tree != null || !stack.isEmpty()) {
while (tree != null) {
stack.push(tree);
tree = tree.left;
}
if (!stack.isEmpty()) {
tree = stack.pop();
System.out.println(tree.val);
tree = tree.right;
}
}
}
我们来对他改造一下，就是在访问每个节点的时候交换，代码如下
public static TreeNode Mirror(TreeNode root) {
//如果为空直接返回
if (root == null)
return null;
Stack<treenode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left;
}
if (!stack.isEmpty()) {
node = stack.pop();
//子节点交换
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
//注意这里以前是node.right，因为上面已经交换了
//，所以这里要改为node.left
node = node.left;
}
}
return root;
}
4，递归方式解决 二叉树中序遍历的递归代码如下
public void inOrderTraversal(TreeNode node) {
if (node == null)
return;
inOrderTraversal(node.left);
System.out.println(node.val);
inOrderTraversal(node.right);
}
上面说了，只要能访问二叉树的每一个节点，然后交换左右子节点就行了，这里就以二叉树中序遍历递归的方式来看下
public TreeNode Mirror(TreeNode root) {
if (root == null)
return null;
Mirror(root.left);
//子节点交换
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
//上面交换过了，这里root.right要变成root.left
Mirror(root.left);
return root;
}
再来看一个后续遍历的
public TreeNode Mirror(TreeNode root) {
if (root == null)
return null;
TreeNode left = Mirror(root.left);
TreeNode right = Mirror(root.right);
root.left = right;
root.right = left;
return root;
}
5，总结
这题没什么难度，但解法比较多，主要是因为二叉树的遍历方式比较多，如果每一种方式递归和非递归都写的话就更多了，这里不在一直写下去了。
京公网安备 11010502036488号