package yao.demo;     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 BT {         /*                  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 = mirrorCopy(r1);  //      inorderTraversal(mirrorRoot);                     System.out.println(isCompleteBinaryTree(r1));          System.out.println(isCompleteBinaryTreeRec(r1));                 }         private static class TreeNode {          int val;          TreeNode left;          TreeNode right;             public TreeNode(int val) {              this.val = val;          }      }         /**      * 求二叉樹中的節點個數遞歸解法： O(n)      * （1）如果二叉樹為空，節點個數為0       * （2）如果二叉樹不為空，二叉樹節點個數 = 左子樹節點個數 +      *            右子樹節點個數 + 1      */     public static int getNodeNumRec(TreeNode root) {          if (root == null) {              return 0;          } else {              return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;          }      }             /**      *  求二叉樹中的節點個數迭代解法O(n)：基本思想同LevelOrderTraversal，      *  即用一個Queue，在Java里面可以用LinkedList來模擬       */     public static int getNodeNum(TreeNode root) {          if(root == null){              return 0;          }          int count = 1;          Queue<TreeNode> queue = new LinkedList<TreeNode>();          queue.add(root);                     while(!queue.isEmpty()){              TreeNode cur = queue.remove();      // 從隊頭位置移除              if(cur.left != null){           // 如果有左孩子，加到隊尾                  queue.add(cur.left);                  count++;              }              if(cur.right != null){      // 如果有右孩子，加到隊尾                  queue.add(cur.right);                  count++;              }          }                     return count;      }         /**      * 求二叉樹的深度（高度） 遞歸解法： O(n)      * （1）如果二叉樹為空，二叉樹的深度為0       * （2）如果二叉樹不為空，二叉樹的深度 = max(左子樹深度， 右子樹深度) + 1      */     public static int getDepthRec(TreeNode root) {          if (root == null) {              return 0;          }             int leftDepth = getDepthRec(root.left);          int rightDepth = getDepthRec(root.right);          return Math.max(leftDepth, rightDepth) + 1;      }             /**      * 求二叉樹的深度（高度） 迭代解法： O(n)      * 基本思想同LevelOrderTraversal，還是用一個Queue      */     public static int getDepth(TreeNode root) {          if(root == null){              return 0;          }                     int depth = 0;                          // 深度          int currentLevelNodes = 1;      // 當前Level，node的數量          int nextLevelNodes = 0;         // 下一層Level，node的數量                     LinkedList<TreeNode> queue = new LinkedList<TreeNode>();          queue.add(root);                     while( !queue.isEmpty() ){              TreeNode cur = queue.remove();      // 從隊頭位置移除              currentLevelNodes--;            // 減少當前Level node的數量              if(cur.left != null){               // 如果有左孩子，加到隊尾                  queue.add(cur.left);                  nextLevelNodes++;           // 并增加下一層Level node的數量              }              if(cur.right != null){          // 如果有右孩子，加到隊尾                  queue.add(cur.right);                  nextLevelNodes++;              }                             if(currentLevelNodes == 0){ // 說明已經遍歷完當前層的所有節點                  depth++;                       // 增加高度                  currentLevelNodes = nextLevelNodes;     // 初始化下一層的遍歷                  nextLevelNodes = 0;              }          }                     return depth;      }                       /**      * 前序遍歷，中序遍歷，后序遍歷 前序遍歷遞歸解法：       * （1）如果二叉樹為空，空操作       * （2）如果二叉樹不為空，訪問根節點，前序遍歷左子樹，前序遍歷右子樹      */     public static void preorderTraversalRec(TreeNode root) {          if (root == null) {              return;          }          System.out.print(root.val + " ");          preorderTraversalRec(root.left);          preorderTraversalRec(root.right);      }             /**      *  前序遍歷迭代解法：用一個輔助stack，總是把右孩子放進棧      *  http://www.youtube.com/watch?v=uPTCbdHSFg4      */     public static void preorderTraversal(TreeNode root) {          if(root == null){              return;          }                     Stack<TreeNode> stack = new Stack<TreeNode>();      // 輔助stack          stack.push(root);                     while( !stack.isEmpty() ){              TreeNode cur = stack.pop();     // 出棧棧頂元素              System.out.print(cur.val + " ");                             // 關鍵點：要先壓入右孩子，再壓入左孩子，這樣在出棧時會先打印左孩子再打印右孩子              if(cur.right != null){                  stack.push(cur.right);              }              if(cur.left != null){                  stack.push(cur.left);              }          }      }         /**      * 中序遍歷遞歸解法       * （1）如果二叉樹為空，空操作。       * （2）如果二叉樹不為空，中序遍歷左子樹，訪問根節點，中序遍歷右子樹      */     public static void inorderTraversalRec(TreeNode root) {          if (root == null) {              return;          }          inorderTraversalRec(root.left);          System.out.print(root.val + " ");          inorderTraversalRec(root.right);      }             /**      * 中序遍歷迭代解法 ，用棧先把根節點的所有左孩子都添加到棧內，      * 然后輸出棧頂元素，再處理棧頂元素的右子樹      * http://www.youtube.com/watch?v=50v1sJkjxoc      *       * 還有一種方法能不用遞歸和棧，基于線索二叉樹的方法，較麻煩以后補上      * http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/      */     public static void inorderTraversal(TreeNode root){          if(root == null){              return;          }          Stack<TreeNode> stack = new Stack<TreeNode>();          TreeNode cur = root;                     while( true ){              while(cur != null){     // 先添加一個非空節點所有的左孩子到棧                  stack.push(cur);                  cur = cur.left;              }                             if(stack.isEmpty()){                  break;              }                                 // 因為此時已經沒有左孩子了，所以輸出棧頂元素              cur = stack.pop();              System.out.print(cur.val + " ");              cur = cur.right;    // 準備處理右子樹          }      }         /**      * 后序遍歷遞歸解法       * （1）如果二叉樹為空，空操作       * （2）如果二叉樹不為空，后序遍歷左子樹，后序遍歷右子樹，訪問根節點      */     public static void postorderTraversalRec(TreeNode root) {          if (root == null) {              return;          }          postorderTraversalRec(root.left);          postorderTraversalRec(root.right);          System.out.print(root.val + " ");      }             /**      *  后序遍歷迭代解法      *  http://www.youtube.com/watch?v=hv-mJUs5mvU      *        */     public static void postorderTraversal(TreeNode root) {          if (root == null) {              return;          }                     Stack<TreeNode> s = new Stack<TreeNode>();      // 第一個stack用于添加node和它的左右孩子          Stack<TreeNode> output = new Stack<TreeNode>();// 第二個stack用于翻轉第一個stack輸出                     s.push(root);          while( !s.isEmpty() ){      // 確保所有元素都被翻轉轉移到第二個stack              TreeNode cur = s.pop(); // 把棧頂元素添加到第二個stack              output.push(cur);                                    if(cur.left != null){       // 把棧頂元素的左孩子和右孩子分別添加入第一個stack                  s.push(cur.left);              }              if(cur.right != null){                  s.push(cur.right);              }          }                     while( !output.isEmpty() ){ // 遍歷輸出第二個stack，即為后序遍歷              System.out.print(output.pop().val + " ");          }      }         /**      * 分層遍歷二叉樹（按層次從上往下，從左往右）迭代      * 相當于廣度優先搜索，使用隊列實現。隊列初始化，將根節點壓入隊列。當隊列不為空，進行如下操作：彈出一個節點      * ，訪問，若左子節點或右子節點不為空，將其壓入隊列      */     public static void levelTraversal(TreeNode root) {          if (root == null) {              return;          }          LinkedList<TreeNode> queue = new LinkedList<TreeNode>();          queue.push(root);             while (!queue.isEmpty()) {              TreeNode cur = queue.removeFirst();              System.out.print(cur.val + " ");              if (cur.left != null) {                  queue.add(cur.left);              }              if (cur.right != null) {                  queue.add(cur.right);              }          }      }             /**      *  分層遍歷二叉樹（遞歸）      *  很少有人會用遞歸去做level traversal      *  基本思想是用一個大的ArrayList，里面包含了每一層的ArrayList。      *  大的ArrayList的size和level有關系      *        *  這是我目前見到的最好的遞歸解法！      *  http://discuss.leetcode.com/questions/49/binary-tree-level-order-traversal#answer-container-2543      */     public static void levelTraversalRec(TreeNode root) {          ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();          dfs(root, 0, ret);          System.out.println(ret);      }             private static void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> ret){          if(root == null){              return;          }                     // 添加一個新的ArrayList表示新的一層          if(level >= ret.size()){              ret.add(new ArrayList<Integer>());          }                     ret.get(level).add(root.val);   // 把節點添加到表示那一層的ArrayList里          dfs(root.left, level+1, ret);       // 遞歸處理下一層的左子樹和右子樹          dfs(root.right, level+1, ret);      }                /**      * 將二叉查找樹變為有序的雙向鏈表 要求不能創建新節點，只調整指針。       * 遞歸解法：      * 參考了http://stackoverflow.com/questions/11511898/converting-a-binary-search-tree-to-doubly-linked-list#answer-11530016      * 感覺是最清晰的遞歸解法，但要注意遞歸完，root會在鏈表的中間位置，因此要手動      * 把root移到鏈表頭或鏈表尾      */     public static TreeNode convertBST2DLLRec(TreeNode root) {          root = convertBST2DLLSubRec(root);                     // root會在鏈表的中間位置，因此要手動把root移到鏈表頭          while(root.left != null){              root = root.left;          }          return root;      }             /**      *  遞歸轉換BST為雙向鏈表(DLL)      */     public static TreeNode convertBST2DLLSubRec(TreeNode root){          if(root==null || (root.left==null && root.right==null)){              return root;          }                     TreeNode tmp = null;          if(root.left != null){          // 處理左子樹              tmp = convertBST2DLLSubRec(root.left);              while(tmp.right != null){   // 尋找最右節點                  tmp = tmp.right;              }              tmp.right = root;       // 把左子樹處理后結果和root連接              root.left = tmp;          }          if(root.right != null){     // 處理右子樹              tmp = convertBST2DLLSubRec(root.right);              while(tmp.left != null){    // 尋找最左節點                  tmp = tmp.left;              }              tmp.left = root;        // 把右子樹處理后結果和root連接              root.right = tmp;          }          return root;      }             /**      * 將二叉查找樹變為有序的雙向鏈表 迭代解法 //   * 類似inorder traversal的做法      */     public static TreeNode convertBST2DLL(TreeNode root) {          if(root == null){              return null;          }          Stack<TreeNode> stack = new Stack<TreeNode>();          TreeNode cur = root;        // 指向當前處理節點          TreeNode old = null;            // 指向前一個處理的節點          TreeNode head = null;       // 鏈表頭                     while( true ){              while(cur != null){     // 先添加一個非空節點所有的左孩子到棧                  stack.push(cur);                  cur = cur.left;              }                             if(stack.isEmpty()){                  break;              }                                 // 因為此時已經沒有左孩子了，所以輸出棧頂元素              cur = stack.pop();              if(old != null){                  old.right = cur;              }              if(head == null){       // /第一個節點為雙向鏈表頭節點                  head = cur;              }                             old = cur;          // 更新old              cur = cur.right;    // 準備處理右子樹          }                     return head;      }         /**      * 求二叉樹第K層的節點個數   遞歸解法：       * （1）如果二叉樹為空或者k<1返回0      * （2）如果二叉樹不為空并且k==1，返回1      * （3）如果二叉樹不為空且k>1，返回root左子樹中k-1層的節點個數與root右子樹k-1層節點個數之和      *       * 求以root為根的k層節點數目 等價于 求以root左孩子為根的k-1層（因為少了root那一層）節點數目 加上      * 以root右孩子為根的k-1層（因為少了root那一層）節點數目      *       * 所以遇到樹，先把它拆成左子樹和右子樹，把問題降解      *       */     public static int getNodeNumKthLevelRec(TreeNode root, int k) {          if (root == null || k < 1) {              return 0;          }             if (k == 1) {              return 1;          }          int numLeft = getNodeNumKthLevelRec(root.left, k - 1);      // 求root左子樹的k-1層節點數          int numRight = getNodeNumKthLevelRec(root.right, k - 1);    // 求root右子樹的k-1層節點數          return numLeft + numRight;      }             /**      *  求二叉樹第K層的節點個數   迭代解法：       *  同getDepth的迭代解法      */     public static int getNodeNumKthLevel(TreeNode root, int k){          if(root == null){              return 0;          }          Queue<TreeNode> queue = new LinkedList<TreeNode>();          queue.add(root);                     int i = 1;          int currentLevelNodes = 1;      // 當前Level，node的數量          int nextLevelNodes = 0;         // 下一層Level，node的數量                     while( !queue.isEmpty() && i<k){              TreeNode cur = queue.remove();      // 從隊頭位置移除              currentLevelNodes--;            // 減少當前Level node的數量              if(cur.left != null){               // 如果有左孩子，加到隊尾                  queue.add(cur.left);                  nextLevelNodes++;           // 并增加下一層Level node的數量              }              if(cur.right != null){          // 如果有右孩子，加到隊尾                  queue.add(cur.right);                  nextLevelNodes++;              }                             if(currentLevelNodes == 0){ // 說明已經遍歷完當前層的所有節點                  currentLevelNodes = nextLevelNodes;     // 初始化下一層的遍歷                  nextLevelNodes = 0;                  i++;            // 進入到下一層              }          }                     return currentLevelNodes;      }         /**      * 求二叉樹中葉子節點的個數（遞歸）      */     public static int getNodeNumLeafRec(TreeNode root) {          // 當root不存在，返回空          if (root == null) {              return 0;          }             // 當為葉子節點時返回1          if (root.left == null && root.right == null) {              return 1;          }             // 把一個樹拆成左子樹和右子樹之和，原理同上一題          return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right);      }             /**      *  求二叉樹中葉子節點的個數（迭代）      *  還是基于Level order traversal      */     public static int getNodeNumLeaf(TreeNode root) {          if(root == null){              return 0;          }          Queue<TreeNode> queue = new LinkedList<TreeNode>();          queue.add(root);                     int leafNodes = 0;              // 記錄上一個Level，node的數量                     while( !queue.isEmpty() ){              TreeNode cur = queue.remove();      // 從隊頭位置移除              if(cur.left != null){               // 如果有左孩子，加到隊尾                  queue.add(cur.left);              }              if(cur.right != null){              // 如果有右孩子，加到隊尾                  queue.add(cur.right);              }              if(cur.left==null && cur.right==null){          // 葉子節點                  leafNodes++;              }          }                     return leafNodes;      }         /**      * 判斷兩棵二叉樹是否相同的樹。      * 遞歸解法：       * （1）如果兩棵二叉樹都為空，返回真      * （2）如果兩棵二叉樹一棵為空，另一棵不為空，返回假       * （3）如果兩棵二叉樹都不為空，如果對應的左子樹和右子樹都同構返回真，其他返回假      */     public static boolean isSameRec(TreeNode r1, TreeNode r2) {          // 如果兩棵二叉樹都為空，返回真          if (r1 == null && r2 == null) {              return true;          }          // 如果兩棵二叉樹一棵為空，另一棵不為空，返回假          else if (r1 == null || r2 == null) {              return false;          }             if(r1.val != r2.val){              return false;          }          boolean leftRes = isSameRec(r1.left, r2.left);      // 比較對應左子樹          boolean rightRes = isSameRec(r1.right, r2.right); // 比較對應右子樹          return leftRes && rightRes;      }             /**      * 判斷兩棵二叉樹是否相同的樹（迭代）      * 遍歷一遍即可，這里用preorder      */     public static boolean isSame(TreeNode r1, TreeNode r2) {          // 如果兩個樹都是空樹，則返回true          if(r1==null && r2==null){              return true;          }                     // 如果有一棵樹是空樹，另一顆不是，則返回false          if(r1==null || r2==null){              return false;          }                     Stack<TreeNode> s1 = new Stack<TreeNode>();          Stack<TreeNode> s2 = new Stack<TreeNode>();                     s1.push(r1);          s2.push(r2);                     while(!s1.isEmpty() && !s2.isEmpty()){              TreeNode n1 = s1.pop();              TreeNode n2 = s2.pop();              if(n1==null && n2==null){                  continue;              }else if(n1!=null && n2!=null && n1.val==n2.val){                  s1.push(n1.right);                  s1.push(n1.left);                  s2.push(n2.right);                  s2.push(n2.left);              }else{                  return false;              }          }          return true;      }         /**      * 判斷二叉樹是不是平衡二叉樹 遞歸解法：       * （1）如果二叉樹為空，返回真      * （2）如果二叉樹不為空，如果左子樹和右子樹都是AVL樹并且左子樹和右子樹高度相差不大于1，返回真，其他返回假      */     public static boolean isAVLRec(TreeNode root) {          if(root == null){           // 如果二叉樹為空，返回真              return true;          }                     // 如果左子樹和右子樹高度相差大于1，則非平衡二叉樹, getDepthRec()是前面實現過的求樹高度的方法          if(Math.abs(getDepthRec(root.left) - getDepthRec(root.right)) > 1){              return false;          }                     // 遞歸判斷左子樹和右子樹是否為平衡二叉樹          return isAVLRec(root.left) && isAVLRec(root.right);      }                /**      * 求二叉樹的鏡像 遞歸解法：       * （1）如果二叉樹為空，返回空      * （2）如果二叉樹不為空，求左子樹和右子樹的鏡像，然后交換左子樹和右子樹      */     // 1. 破壞原來的樹，把原來的樹改成其鏡像      public static TreeNode mirrorRec(TreeNode root) {          if (root == null) {              return null;          }             TreeNode left = mirrorRec(root.left);          TreeNode right = mirrorRec(root.right);             root.left = right;          root.right = left;          return root;      }             // 2. 不能破壞原來的樹，返回一個新的鏡像樹      public static TreeNode mirrorCopyRec(TreeNode root){          if(root == null){              return null;          }                     TreeNode newNode = new TreeNode(root.val);          newNode.left = mirrorCopyRec(root.right);          newNode.right = mirrorCopyRec(root.left);                     return newNode;      }             // 3. 判斷兩個樹是否互相鏡像      public static boolean isMirrorRec(TreeNode r1, TreeNode r2){          // 如果兩個樹都是空樹，則返回true          if(r1==null && r2==null){              return true;          }                     // 如果有一棵樹是空樹，另一顆不是，則返回false          if(r1==null || r2==null){              return false;          }                     // 如果兩個樹都非空樹，則先比較根節點          if(r1.val != r2.val){              return false;          }                     // 遞歸比較r1的左子樹的鏡像是不是r2右子樹 和           // r1的右子樹的鏡像是不是r2左子樹          return isMirrorRec(r1.left, r2.right) && isMirrorRec(r1.right, r2.left);      }             // 1. 破壞原來的樹，把原來的樹改成其鏡像      public static void mirror(TreeNode root) {          if(root == null){              return;          }                     Stack<TreeNode> stack = new Stack<TreeNode>();          stack.push(root);          while( !stack.isEmpty() ){              TreeNode cur = stack.pop();                             // 交換左右孩子              TreeNode tmp = cur.right;              cur.right = cur.left;              cur.left = tmp;                             if(cur.right != null){                  stack.push(cur.right);              }              if(cur.left != null){                  stack.push(cur.left);              }          }      }             // 2. 不能破壞原來的樹，返回一個新的鏡像樹      public static TreeNode mirrorCopy(TreeNode root){          if(root == null){              return null;          }                     Stack<TreeNode> stack = new Stack<TreeNode>();          Stack<TreeNode> newStack = new Stack<TreeNode>();          stack.push(root);          TreeNode newRoot = new TreeNode(root.val);          newStack.push(newRoot);                     while( !stack.isEmpty() ){              TreeNode cur = stack.pop();              TreeNode newCur = newStack.pop();                             if(cur.right != null){                  stack.push(cur.right);                  newCur.left = new TreeNode(cur.right.val);                  newStack.push(newCur.left);              }              if(cur.left != null){                  stack.push(cur.left);                  newCur.right = new TreeNode(cur.left.val);                  newStack.push(newCur.right);              }          }                     return newRoot;      }                /**      * 求二叉樹中兩個節點的最低公共祖先節點       * 遞歸解法：       * （1）如果兩個節點分別在根節點的左子樹和右子樹，則返回根節點      * （2）如果兩個節點都在左子樹，則遞歸處理左子樹；如果兩個節點都在右子樹，則遞歸處理右子樹      */     public static TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2) {          if (findNodeRec(root.left, n1)) {               // 如果n1在樹的左子樹              if (findNodeRec(root.right, n2)) {      // 如果n2在樹的右子樹                  return root;                                // 返回根節點              } else {            // 如果n2也在樹的左子樹                  return getLastCommonParentRec(root.left, n1, n2); // 遞歸處理              }          } else {                // 如果n1在樹的右子樹              if (findNodeRec(root.left, n2)) {           // 如果n2在左子樹                  return root;              } else {                 // 如果n2在右子樹                  return getLastCommonParentRec(root.right, n1, n2); // 遞歸處理              }          }      }         // 幫助方法，遞歸判斷一個點是否在樹里      private static boolean findNodeRec(TreeNode root, TreeNode node) {          if (root == null || node == null) {              return false;          }          if (root == node) {              return true;          }             // 先嘗試在左子樹中查找          boolean found = findNodeRec(root.left, node);          if (!found) {       // 如果查找不到，再在右子樹中查找              found = findNodeRec(root.right, node);          }          return found;      }             // 求二叉樹中兩個節點的最低公共祖先節點 （更加簡潔版的遞歸）      public static TreeNode getLastCommonParentRec2(TreeNode root, TreeNode n1, TreeNode n2) {          if(root == null){              return null;          }                     // 如果有一個match，則說明當前node就是要找的最低公共祖先          if(root.equals(n1) || root.equals(n2)){              return root;          }          TreeNode commonInLeft = getLastCommonParentRec2(root.left, n1, n2);          TreeNode commonInRight = getLastCommonParentRec2(root.right, n1, n2);                     // 如果一個左子樹找到，一個在右子樹找到，則說明root是唯一可能的最低公共祖先          if(commonInLeft!=null && commonInRight!=null){              return root;          }                     // 其他情況是要不然在左子樹要不然在右子樹          if(commonInLeft != null){              return commonInLeft;          }                     return commonInRight;      }         /**      * 非遞歸解法：       * 先求從根節點到兩個節點的路徑，然后再比較對應路徑的節點就行，最后一個相同的節點也就是他們在二叉樹中的最低公共祖先節點      */     public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2) {          if (root == null || n1 == null || n2 == null) {              return null;          }             ArrayList<TreeNode> p1 = new ArrayList<TreeNode>();          boolean res1 = getNodePath(root, n1, p1);          ArrayList<TreeNode> p2 = new ArrayList<TreeNode>();          boolean res2 = getNodePath(root, n2, p2);             if (!res1 || !res2) {              return null;          }             TreeNode last = null;          Iterator<TreeNode> iter1 = p1.iterator();          Iterator<TreeNode> iter2 = p2.iterator();             while (iter1.hasNext() && iter2.hasNext()) {              TreeNode tmp1 = iter1.next();              TreeNode tmp2 = iter2.next();              if (tmp1 == tmp2) {                  last = tmp1;              } else { // 直到遇到非公共節點                  break;              }          }          return last;      }         // 把從根節點到node路徑上所有的點都添加到path中      private static boolean getNodePath(TreeNode root, TreeNode node, ArrayList<TreeNode> path) {          if (root == null) {              return false;          }                     path.add(root);     // 把這個節點加到路徑中          if (root == node) {              return true;          }             boolean found = false;          found = getNodePath(root.left, node, path); // 先在左子樹中找                     if (!found) {               // 如果沒找到，再在右子樹找              found = getNodePath(root.right, node, path);          }          if (!found) {               // 如果實在沒找到證明這個節點不在路徑中，說明剛才添加進去的不是路徑上的節點，刪掉！              path.remove(root);            }             return found;      }         /**      * 求二叉樹中節點的最大距離 即二叉樹中相距最遠的兩個節點之間的距離。 (distance / diameter)      * 遞歸解法：       * （1）如果二叉樹為空，返回0，同時記錄左子樹和右子樹的深度，都為0      * （2）如果二叉樹不為空，最大距離要么是左子樹中的最大距離，要么是右子樹中的最大距離，      * 要么是左子樹節點中到根節點的最大距離+右子樹節點中到根節點的最大距離，      * 同時記錄左子樹和右子樹節點中到根節點的最大距離。      *       * http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html      *       * 計算一個二叉樹的最大距離有兩個情況:           情況A: 路徑經過左子樹的最深節點，通過根節點，再到右子樹的最深節點。         情況B: 路徑不穿過根節點，而是左子樹或右子樹的最大距離路徑，取其大者。         只需要計算這兩個情況的路徑距離，并取其大者，就是該二叉樹的最大距離      */     public static Result getMaxDistanceRec(TreeNode root){          if(root == null){              Result empty = new Result(0, -1);       // 目的是讓調用方 +1 后，把當前的不存在的 (NULL) 子樹當成最大深度為 0              return empty;          }                     // 計算出左右子樹分別最大距離          Result lmd = getMaxDistanceRec(root.left);          Result rmd = getMaxDistanceRec(root.right);                     Result res = new Result();          res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) + 1;        // 當前最大深度          // 取情況A和情況B中較大值          res.maxDistance = Math.max( lmd.maxDepth+rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance) );          return res;      }             private static class Result{          int maxDistance;          int maxDepth;          public Result() {          }             public Result(int maxDistance, int maxDepth) {              this.maxDistance = maxDistance;              this.maxDepth = maxDepth;          }      }             /**      * 13. 由前序遍歷序列和中序遍歷序列重建二叉樹（遞歸）      * 感覺這篇是講的最為清晰的:      * http://crackinterviewtoday.Wordpress.com/2010/03/15/rebuild-a-binary-tree-from-inorder-and-preorder-traversals/      * 文中還提到一種避免開額外空間的方法，等下次補上      */     public static TreeNode rebuildBinaryTreeRec(List<Integer> preOrder, List<Integer> inOrder){          TreeNode root = null;          List<Integer> leftPreOrder;          List<Integer> rightPreOrder;          List<Integer> leftInorder;          List<Integer> rightInorder;          int inorderPos;          int preorderPos;              if ((preOrder.size() != 0) && (inOrder.size() != 0))          {              // 把preorder的第一個元素作為root              root = new TreeNode(preOrder.get(0));                  //  Based upon the current node data seperate the traversals into leftPreorder, rightPreorder,              //  leftInorder, rightInorder lists              // 因為知道root節點了，所以根據root節點位置，把preorder，inorder分別劃分為 root左側 和 右側 的兩個子區間              inorderPos = inOrder.indexOf(preOrder.get(0));      // inorder序列的分割點              leftInorder = inOrder.subList(0, inorderPos);              rightInorder = inOrder.subList(inorderPos + 1, inOrder.size());                  preorderPos = leftInorder.size();                           // preorder序列的分割點              leftPreOrder = preOrder.subList(1, preorderPos + 1);              rightPreOrder = preOrder.subList(preorderPos + 1, preOrder.size());                  root.left = rebuildBinaryTreeRec(leftPreOrder, leftInorder);        // root的左子樹就是preorder和inorder的左側區間而形成的樹              root.right = rebuildBinaryTreeRec(rightPreOrder, rightInorder); // root的右子樹就是preorder和inorder的右側區間而形成的樹          }              return root;      }             /**         14.  判斷二叉樹是不是完全二叉樹（迭代）         若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，         第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹。         有如下算法，按層次（從上到下，從左到右）遍歷二叉樹，當遇到一個節點的左子樹為空時，         則該節點右子樹必須為空，且后面遍歷的節點左右子樹都必須為空，否則不是完全二叉樹。      */     public static boolean isCompleteBinaryTree(TreeNode root){          if(root == null){              return false;          }                     Queue<TreeNode> queue = new LinkedList<TreeNode>();          queue.add(root);          boolean mustHaveNoChild = false;          boolean result = true;                     while( !queue.isEmpty() ){              TreeNode cur = queue.remove();              if(mustHaveNoChild){    // 已經出現了有空子樹的節點了，后面出現的必須為葉節點（左右子樹都為空）                    if(cur.left!=null || cur.right!=null){                      result = false;                      break;                  }              } else {                  if(cur.left!=null && cur.right!=null){      // 如果左子樹和右子樹都非空，則繼續遍歷                      queue.add(cur.left);                      queue.add(cur.right);                  }else if(cur.left!=null && cur.right==null){    // 如果左子樹非空但右子樹為空，說明已經出現空節點，之后必須都為空子樹                      mustHaveNoChild = true;                      queue.add(cur.left);                  }else if(cur.left==null && cur.right!=null){    // 如果左子樹為空但右子樹非空，說明這棵樹已經不是完全二叉完全樹！                      result = false;                      break;                  }else{          // 如果左右子樹都為空，則后面的必須也都為空子樹                      mustHaveNoChild = true;                  }              }          }          return result;      }             /**      * 14.  判斷二叉樹是不是完全二叉樹（遞歸）      * http://stackoverflow.com/questions/1442674/how-to-determine-whether-a-binary-tree-is-complete      *       */     public static boolean isCompleteBinaryTreeRec(TreeNode root){  //      Pair notComplete = new Pair(-1, false);  //      return !isCompleteBinaryTreeSubRec(root).equalsTo(notComplete);          return isCompleteBinaryTreeSubRec(root).height != -1;      }             // 遞歸判斷是否滿樹（完美）      public static boolean isPerfectBinaryTreeRec(TreeNode root){          return isCompleteBinaryTreeSubRec(root).isFull;      }             // 遞歸，要創建一個Pair class來保存樹的高度和是否已滿的信息      public static Pair isCompleteBinaryTreeSubRec(TreeNode root){          if(root == null){              return new Pair(0, true);          }                     Pair left = isCompleteBinaryTreeSubRec(root.left);          Pair right = isCompleteBinaryTreeSubRec(root.right);                     // 左樹滿節點，而且左右樹相同高度，則是唯一可能形成滿樹（若右樹也是滿節點）的情況          if(left.isFull && left.height==right.height){              return new Pair(1+left.height, right.isFull);          }                     // 左樹非滿，但右樹是滿節點，且左樹高度比右樹高一          // 注意到如果其左樹為非完全樹，則它的高度已經被設置成-1，          // 因此不可能滿足第二個條件！          if(right.isFull && left.height==right.height+1){              return new Pair(1+left.height, false);          }                     // 其他情況都是非完全樹，直接設置高度為-1          return new Pair(-1, false);      }             private static class Pair{          int height;             // 樹的高度          boolean isFull;     // 是否是個滿樹             public Pair(int height, boolean isFull) {              this.height = height;              this.isFull = isFull;          }             @SuppressWarnings("unused")		public boolean equalsTo(Pair obj){              return this.height==obj.height && this.isFull==obj.isFull;          }      }         }