求解二叉树镜像-白红宇

一，问题介绍

求解一棵二叉树的镜像。所谓镜像，就是从二叉树的根到叶结点的每一层，将所有的非叶子结点的孩子进行交换。

比如说，下面两棵二叉树互为镜像：

二，算法分析

1 /** 2      * 递归求解二叉树的镜像 3      * @param root 4      */ 5     public void mirrorRecursively(BinaryNode
     
       root){ 6         //base condition 7         if(root == null || (root.left == null && root.right == null)) 8             return; 9         10         //swap nodes11         BinaryNode
      
        tmp;12         tmp = root.left;13         root.left = root.right;14         root.right = tmp;15         16         //recursively call17         if(root.left != null)18             mirrorRecursively(root.left);19         if(root.right != null)20             mirrorRecursively(root.right);21     }

从根结点开始，先交换根结点的左右孩子，然后再依次交换根结点的左右孩子的孩子......

时间复杂度分析：由于每个结点都会遍历一次，故时间复杂度为O(N)，也可以列出递归表达式如下：

递归表达式：T(N)=2T(N/2)+O(1). 由17行到20行的两个if语句，可知将问题规模为N分解成了两个规模为N/2的两个子问题；附加的处理规模为O(1)

解得T(N)=O(N)

尾递归转化为循环：

1 /** 2      * 循环实现 求解二叉树的镜像 3      * @param root 4      */ 5     public void mirrorLoop(BinaryNode
     
       root){ 6         if(root == null || (root.left == null && root.right == null)) 7             return; 8          9         swap(root.left, root.right, root);//根的左右孩子的交换10         11         //处理根的左子树的交换12         BinaryNode
      
        currentNode = root;13         while(currentNode.left != null)14         {15             currentNode = currentNode.left;16             swap(currentNode.left, currentNode.right, currentNode);17         }18 19         //处理根的右子树的交换20         currentNode = root;21         while(currentNode.right != null)22         {23             currentNode = currentNode.right;24             swap(currentNode.left, currentNode.right, currentNode);25         }26     }

三，完整代码实现

递归实现和非递归实现。由于该递归是一个尾递归，故非递归实现也很简单。

1 public class BinaryTree_Mirror
     
      > {  2       3     private static class BinaryNode
      
       {  4         T element;  5         BinaryNode
       
         left;  6         BinaryNode
        
          right;  7           8         public BinaryNode(T element) {  9             this.element = element; 10             left = right = null; 11         } 12          13         @Override 14         public String toString() { 15             return element.toString(); 16         } 17     } 18      19     private BinaryNode
         
           root; 20      21     /** 22      * 向二叉树中插入一个元素 23      * @param element 24      */ 25     public void insert(T element){ 26         root = insert(root, element); 27     } 28     private BinaryNode
          
            insert(BinaryNode
           
             root, T element){ 29 if(root == null) 30 return new BinaryNode
            
             (element); 31 int r = (int)(2*Math.random()); 32 //随机地将元素插入到左子树 或者 右子树中 33 if(r==0) 34 root.left = insert(root.left, element); 35 else 36 root.right = insert(root.right, element); 37 return root; 38 } 39 40 public void inOrder(BinaryNode
             
               root){ 41 //base condition 42 if(root == null) 43 return; 44 45 inOrder(root.left); 46 System.out.print(root + " ");//visit node 47 inOrder(root.right); 48 } 49 50 51 /** 52 * 递归求解二叉树的镜像 53 * @param root 54 */ 55 public void mirrorRecursively(BinaryNode
              
                root){ 56 //base condition 57 if(root == null || (root.left == null && root.right == null)) 58 return; 59 60 //swap nodes 61 BinaryNode
               
                 tmp; 62 tmp = root.left; 63 root.left = root.right; 64 root.right = tmp; 65 66 //recursively call 67 if(root.left != null) 68 mirrorRecursively(root.left); 69 if(root.right != null) 70 mirrorRecursively(root.right); 71 } 72 73 /** 74 * 循环实现 求解二叉树的镜像 75 * @param root 76 */ 77 public void mirrorLoop(BinaryNode
                
                  root){ 78 if(root == null || (root.left == null && root.right == null)) 79 return; 80 81 swap(root.left, root.right, root); 82 83 BinaryNode
                 
                   currentNode = root; 84 while(currentNode.left != null) 85 { 86 currentNode = currentNode.left; 87 swap(currentNode.left, currentNode.right, currentNode); 88 } 89 90 currentNode = root; 91 while(currentNode.right != null) 92 { 93 currentNode = currentNode.right; 94 swap(currentNode.left, currentNode.right, currentNode); 95 } 96 } 97 98 /** 99 * 交换currentNode的左右孩子结点100 * @param left101 * @param right102 * @param currentNode103 */104 private void swap(BinaryNode
                  
                    left, BinaryNode
                   
                     right, BinaryNode
                    
                      currentNode){105 BinaryNode
                     
                       tmpNode;106 tmpNode = currentNode.left;107 currentNode.left = currentNode.right;108 currentNode.right = tmpNode;109 }110 111 112 public static void main(String[] args) {113 BinaryTree_Mirror
                      
                        tree1 = new BinaryTree_Mirror<>();114 BinaryTree_Mirror
                       
                         tree2 = new BinaryTree_Mirror<>();115 116 int[] ele = C2_2_8.algorithm1(4);117 for (int i = 0; i < ele.length; i++) {118 tree1.insert(ele[i]);119 tree2.insert(ele[i]);120 }121 122 tree1.mirrorLoop(tree1.root);123 tree2.mirrorRecursively(tree2.root);124 125 tree1.inOrder(tree1.root);126 System.out.println();127 tree2.inOrder(tree2.root);128 }129 }

本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/p/5553846.html，如需转载请自行联系原作者