面试大总结之二：Java搞定面试中的二叉树题目 - JAVA

 
package BinaryTreeSummary;  
  
import java.util.ArrayList;  
import java.util.Iterator;  
import java.util.LinkedList;  
import java.util.List;  
import java.util.Queue;  
import java.util.Stack;  
  
/** 
 * http://blog.csdn.net/luckyxiaoqiang/article/details/7518888  轻松搞定面试中的二叉树题目 
 * http://www.cnblogs.com/Jax/archive/2009/12/28/1633691.html  算法大全（3） 二叉树 
 *  
 * TODO: 一定要能熟练地写出所有问题的递归和非递归做法！ 
 * 
 * 1. 求二叉树中的节点个数: getNodeNumRec（递归），getNodeNum（迭代） 
 * 2. 求二叉树的深度: getDepthRec（递归），getDepth  
 * 3. 前序遍历，中序遍历，后序遍历: preorderTraversalRec, preorderTraversal, inorderTraversalRec, postorderTraversalRec 
 * (https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_2) 
 * 4.分层遍历二叉树（按层次从上往下，从左往右）: levelTraversal, levelTraversalRec（递归解法！） 
 * 5. 将二叉查找树变为有序的双向链表: convertBST2DLLRec, convertBST2DLL 
 * 6. 求二叉树第K层的节点个数：getNodeNumKthLevelRec, getNodeNumKthLevel 
 * 7. 求二叉树中叶子节点的个数：getNodeNumLeafRec, getNodeNumLeaf 
 * 8. 判断两棵二叉树是否相同的树：isSameRec, isSame 
 * 9. 判断二叉树是不是平衡二叉树：isAVLRec 
 * 10. 求二叉树的镜像（破坏和不破坏原来的树两种情况）：mirrorRec, mirrorCopyRec 
 * 10.1 判断两个树是否互相镜像：isMirrorRec 
 * 11. 求二叉树中两个节点的最低公共祖先节点：getLastCommonParent, getLastCommonParentRec, getLastCommonParentRec2 
 * 12. 求二叉树中节点的最大距离：getMaxDistanceRec 
 * 13. 由前序遍历序列和中序遍历序列重建二叉树：rebuildBinaryTreeRec 
 * 14.判断二叉树是不是完全二叉树：isCompleteBinaryTree, isCompleteBinaryTreeRec 
 *  
 */  
public class Demo {  
  
    /* 
                 1  
                / \  
               2   3  
              / \   \  
             4  5   6  
     */  
    public static void main(String[] args) {  
        TreeNode r1 = new TreeNode(1);  
        TreeNode r2 = new TreeNode(2);  
        TreeNode r3 = new TreeNode(3);  
        TreeNode r4 = new TreeNode(4);  
        TreeNode r5 = new TreeNode(5);  
        TreeNode r6 = new TreeNode(6);  
          
        r1.left = r2;  
        r1.right = r3;  
     




   r2.left = r4;  
        r2.right = r5;  
        r3.right = r6;  
          
//      System.out.println(getNodeNumRec(r1));  
//      System.out.println(getNodeNum(r1));  
//      System.out.println(getDepthRec(r1));  
//      System.out.println(getDepth(r1));  
          
//      preorderTraversalRec(r1);  
//      System.out.println();  
//      preorderTraversal(r1);  
//      System.out.println();  
//      inorderTraversalRec(r1);  
//      System.out.println();  
//      inorderTraversal(r1);  
//      System.out.println();  
//      postorderTraversalRec(r1);  
//      System.out.println();  
//      postorderTraversal(r1);  
//      System.out.println();  
//      levelTraversal(r1);  
//      System.out.println();  
//      levelTraversalRec(r1);  
//      System.out.println();  
          
//      TreeNode tmp = convertBSTRec(r1);  
//      while(true){  
//          if(tmp == null){  
//              break;  
//          }  
//          System.out.print(tmp.val + " ");  
//          if(tmp.right == null){  
//              break;  
//          }  
//          tmp = tmp.right;  
//      }  
//      System.out.println();  
//      while(true){  
//          if(tmp == null){  
//              break;  
//          }  
//          System.out.print(tmp.val + " ");  
//          if(tmp.left == null){  
//              break;  
//          }  
//          tmp = tmp.left;  
//      }  
          
          
//      TreeNode tmp = convertBST2DLL(r1);  
//      while(true){  
//          if(tmp == null){  
//              break;  
//          }  
//          System.out.print(tmp.val + " ");  
//          if(tmp.right == null){  
//              break;  
//          }  
//          tmp = tmp.right;  
//      }  
          
//      System.out.println(getNodeNumKthLevelRec(r1, 2));  
//      System.out.println(getNodeNumKthLevel(r1, 2));  
          
//      System.out.println(getNodeNumLeafRec(r1));  
//      System.out.println(getNodeNumLeaf(r1));  
          
//      System.out.println(isSame(r1, r1));  
//      inorderTraversal(r1);  
//      System.out.println();  
//      mirror(r1);  
//      TreeNode mirrorRoot = mirrorCop
面试大总结之二：Java搞定面试中的二叉树题目(一)
