您的位置: 首页  >  文章  >  反转二叉树（二叉树的镜像）

反转二叉树（二叉树的镜像）

分类: 文章 • 2024-01-07 12:50:34


反转二叉树（二叉树的镜像）

    输入一个二叉树，输出其镜像。

    如下图，即交换所有节点的左右子树。

反转二叉树（二叉树的镜像）


    这里提供两种思路：使用递归和不使用递归。

    使用的二叉树定义如下：

[java] view plain copy
  1. public class TreeNode {  
  2.     int val = 0;  
  3.     TreeNode left = null;  
  4.     TreeNode right = null;  
  5.   
  6.     public TreeNode(int val) {  
  7.         this.val = val;  
  8.   
  9.     }  
  10. }  

    解决方法：

[java] view plain copy
  1. import java.util.LinkedList;  
  2. import java.util.Scanner;  
  3.   
  4. /* 
  5.  * 题目描述：输入一个二叉树，输出其镜像。 
  6.  * */  
  7. public class Solution {  
  8.     Scanner scanner = new Scanner(System.in);  
  9.       
  10.     // 建立二叉树  
  11.     public TreeNode createTree(TreeNode root) {  
  12.         String val;  
  13.         val = scanner.next(); // next方法每次取到一个间隔符前面的数据  
  14.         if(val.equals("#")) {  
  15.             return null;  
  16.         }  
  17.         root = new TreeNode(Integer.parseInt(val));//  System.out.println("输入的数据为：" + val);  
  18.         root.left = createTree(root.left);  
  19.         root.right = createTree(root.right);  
  20.         return root;  
  21.     }  
  22.     // 得到二叉树的镜像  —— 递归的方式  
  23.     public void Mirror(TreeNode root) {  
  24.         if(root == null) {  
  25.             return;  
  26.         }  
  27.         if((root.left == null) && (root.right == null)) {  
  28.             return;  
  29.         }  
  30.         TreeNode temp = root.left;  
  31.         root.left = root.right;  
  32.         root.right = temp;  
  33.         Mirror(root.left);  
  34.         Mirror(root.right);  
  35.     }  
  36.      // 得到二叉树的镜像 —— 不使用递归  
  37.     public void MirrorNotRecursive(TreeNode root) {  
  38.         java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<TreeNode>();  
  39.         TreeNode temp = null;  
  40.         if(root == null) {  
  41.             return;  
  42.         }  
  43.         queue.add(root);  
  44.         while(queue.size() != 0) {  
  45.             TreeNode node = queue.removeFirst();  
  46.             temp = node.left;  
  47.             node.left = node.right;  
  48.             node.right = temp;  
  49.             if(node.right != null) {  
  50.                 queue.add(node.right);  // 入队的为原来的左孩子  
  51.             }  
  52.             if(node.left != null) {  
  53.                 queue.add(node.left);  
  54.             }  
  55.         }  
  56.     }  
  57.       
  58.     // 层次遍历二叉树  
  59.     public void levelTraverse(TreeNode root) {  
  60.         if (root == null) {  
  61.              return;  
  62.         }  
  63.          LinkedList<TreeNode> list = new LinkedList<TreeNode>();  
  64.          list.add(root);  
  65.          while (list.size() != 0) {  
  66.             TreeNode node = list.removeFirst(); // list.removeFirst() 该方法LinkedList才有  
  67.             System.out.print(node.val + " ");  
  68.             if(node.left != null) {  
  69.                  list.add(node.left);  // list.add()添加单个元素，如果不指定索引的话，元素将被添加到链表的最后  
  70.             }  
  71.             if(node.right != null) {  
  72.                 list.add(node.right);  
  73.             }  
  74.         }  
  75.     }  
  76.       
  77.     public static void main(String[] args) {  
  78.         Solution solution = new Solution();  
  79.         TreeNode root = null;  
  80.         root = solution.createTree(root);  
  81.         System.out.println("原二叉树的层次遍历");  
  82.         solution.levelTraverse(root);  
  83.         solution.Mirror(root);  
  84.         System.out.println("\n输出该二叉树的镜像");  
  85.         solution.levelTraverse(root);  
  86.         solution.MirrorNotRecursive(root);  
  87.         System.out.println("\n输出该二叉树的镜像（非递归方式）");  
  88.         solution.levelTraverse(root);  
  89.     }  
  90. }  
  91.   
  92. /* 
  93.  * 测试数据： 
  94.  * 1 2 3 # 4 # # 5 6 # # # 7 8 # # 9 10 # # 11 # #  （说明：其中#说明左右子树为空） 
  95.  * 用先序遍历来建立树后，层次遍历结果为： 1 2 7 3 5 8 9 4 6 10 11 
  96.  * 反转二叉树之后：1 7 2 9 8 5 3 11 10 6 4  
  97.  */  

    上述程序的运行结果为：

    反转二叉树（二叉树的镜像）

    这个代码除实现反转二叉树之外，还实现了先序建立二叉树及层次遍历二叉树，可参见上述代码。关于实现反转二叉树的两种方式，思路参考见下面陈述。

    其中，递归的实现思路参考：http://zhidao.baidu.com/link?url=ohsjZowGYZokAf2wg7Q2w2UIZme_Tt1zuabVWGxFTfpzkmI0hC_BqBlhFAqsNSM3f0393lp0QEBMEp6WDTc0Na

[cpp] view plain copy
  1. void exchangeBTree(BTRee *root)  
  2. {  
  3.   BTRee *t;  
  4.   if(root)  
  5.      {  
  6.          t=root->rChild;  
  7.          root->rChild=root->lChild;  
  8.          root->lChild=t;  
  9.          exchangeBTree(root->lChild);  
  10.          exchangeBTree(root->rChild);  
  11.      }  
  12. }  

   非递归的方式，参考自：

http://www.nowcoder.com/questionTerminal/bcffd7e8a0d4402c99773bed98690bb7?orderByHotValue=0&pos=1

    是借助栈进行操作，栈是后进先出，我实现的时候用LinkedList模拟了队列（先进先出）。这里的区别在于左孩子和右孩子谁先进去，如果要左孩子先出来，可以区分对待：栈需要右孩子先压栈，然后再左孩子；如果是队列，则左孩子入队，然后再是右孩子。

   

[cpp] view plain copy
  1. void NonRecursive_Exchange(TreeNode *T)  
  2. {  
  3.     Stack s;  
  4.     TreeNode *p;  
  5.     if (NULL == T)  
  6.         return;  
  7.     InitStack(&s);  
  8.     Push(&s, T);  
  9.     while (!isEmpty(&s))  
  10.     {  
  11.         T = Pop(&s);  
  12.         p = T->left;  
  13.         T->left = T->right;  
  14.         T->right = p;  
  15.         if (T->right )  
  16.             Push(&s, T->right );  
  17.         if (T->left )  
  18.             Push(&s, T->left );  
  19.     }  
  20.     DestroyStack(&s);  
  21. }  

    最后，该题目可在牛客网进行练习，提交代码：http://www.nowcoder.com/books/coding-interviews/564f4c26aa584921bc75623e48ca3011


相关推荐