本文共 4394 字,大约阅读时间需要 14 分钟。
题目描述:
请完成一个函数,输入一个二叉树,该函数输出它的镜像。思路:
遍历二叉树 如果当前节点存在左子树和右子树 那么将两个子树进行交换1) 递归实现
package com.hqq.exercise.tree;/** * MirrorTree 二叉树的镜像 * 题目描述: * 请完成一个函数,输入一个二叉树,该函数输出它的镜像。 * 思路: * 遍历两个二叉树 如果当前节点存在子节点的话 就交换它的两个子节点 * Created by heqianqian on 2017/8/12. */public class MirrorTree { /** * 输出一个二叉树的镜像[递归] * @param root 二叉树的根节点 */ public static void mirrorTreeByRecursion(BinaryTreeNode root){ if(root == null){ return; } if(root.leftNode==null && root.rightNode == null){ return; } //如果存在子节点 那么就交换它的两个子节点 BinaryTreeNode temp = root.leftNode; root.leftNode = root.rightNode; root.rightNode =temp; if (root.leftNode!=null){ mirrorTreeByRecursion(root.leftNode); } if (root.rightNode!=null){ mirrorTreeByRecursion(root.rightNode); } } /** * 输出一个二叉树的镜像[循环] * @param root 二叉树的根节点 */ public static void mirrorTreeByLoop(BinaryTreeNode root){ while (root!=null&&root.leftNode!=null&&root.rightNode!=null){ //交换节点 BinaryTreeNode temp = root.leftNode; root.leftNode = root.rightNode; root.rightNode = temp; } }}
package com.hqq.exercise.tree;import org.junit.Before;import org.junit.Test;import static org.junit.Assert.*;/** * MirrorTree 二叉树的镜像 * 题目描述: * 请完成一个函数,输入一个二叉树,该函数输出它的镜像。 * 思路: * 遍历两个二叉树 如果当前节点存在子节点的话 就交换它的两个子节点 * 样例输入: * ------8 * ---6 10 * --5 7 9 11 * {8,6,5,7,10,9,11} * 样例输出: * ---------8 * -----10 6 * --11 9 7 5 * {8,10,11,9,6,7,5} * Created by heqianqian on 2017/8/12. */public class MirrorTreeTest { private BinaryTreeNode root; @Before public void setUp() throws Exception { root = new BinaryTreeNode(8); BinaryTreeNode leftChild = new BinaryTreeNode(10); leftChild.leftNode = new BinaryTreeNode(11); leftChild.rightNode = new BinaryTreeNode(9); BinaryTreeNode rightChild = new BinaryTreeNode(6); rightChild.leftNode = new BinaryTreeNode(7); rightChild.rightNode = new BinaryTreeNode(5); root.leftNode = leftChild; root.rightNode = rightChild; System.out.println("Before Mirror"); print(root); System.out.println(); } @Test public void test() throws Exception { MirrorTree.mirrorTreeByRecursion(root); System.out.println("After Mirror"); print(root); } /** * 先序遍历二叉树 */ private void print(BinaryTreeNode root) { System.out.print(root.value + " "); if (root.leftNode != null) { print(root.leftNode); } if (root.rightNode != null) { print(root.rightNode); } }}
运行结果:
Before Mirror8 10 11 9 6 7 5 After Mirror8 6 5 7 10 9 11
2) 非递归实现
1.思路:使用层序遍历+队列实现
层序遍历二叉树 如果当前节点的左右子树不为空 那么交换左右子树 如果左节点非空 左节点入队列 如果右节点非空 右节点入队列public static void mirrorTreeByLoopLevelTraversal(BinaryTreeNode root) { QueuetreeNodeQueue = new LinkedBlockingDeque<>(); while (root != null) { if (root.leftNode != null && root.rightNode != null) { BinaryTreeNode temp = root.leftNode; root.leftNode = root.rightNode; root.rightNode = temp; } if (root.leftNode != null) { treeNodeQueue.add(root.leftNode); } if (root.rightNode != null) { treeNodeQueue.add(root.rightNode); } if (!treeNodeQueue.isEmpty()) { root = treeNodeQueue.poll(); } else { break; } } }
2.使用先序遍历+栈
public static void mirrorTreeByLoopPreTraversal(BinaryTreeNode root) { Stackstack = new Stack<>(); stack.push(root); BinaryTreeNode temp = null; BinaryTreeNode t = null; while (!stack.isEmpty()) { temp = stack.pop(); //如果temp的左右子树不为空 那么交换左右子树 if (temp.leftNode != null && temp.rightNode != null) { t = temp.leftNode; temp.leftNode = temp.rightNode; temp.rightNode = t; } //如果左子树不为空 左子树入栈 if (temp.leftNode != null) { stack.push(temp.leftNode); } //如果右子树不为空 右子树入栈 if (temp.rightNode != null) { stack.push(temp.rightNode); } } }