本文轉(zhuǎn)載自http://blog.csdn.net/fightforyourdream/article/details/16843303
?
題目：?
1. 前序、中序、后序遍歷二叉樹?
2. 層序遍歷二叉樹?
3. 獲得二叉樹的深度?
4. 獲得二叉樹的節(jié)點個數(shù)?
5. 判斷兩棵二叉樹是否為相同的二叉樹?
6. 判斷二叉樹是否為平衡二叉樹?
7. 獲得二叉樹的葉子節(jié)點個數(shù)?
8. 獲得二叉樹第K層上的節(jié)點個數(shù)?
9. 將二叉查找樹變?yōu)橛行虻碾p向鏈表?
10. 求二叉樹中兩個節(jié)點的最低公共祖先節(jié)點?
11. 求二叉樹兩個節(jié)點之間的最大距離?
12. 求從根節(jié)點出發(fā)到node的路徑path?
13. 根據(jù)兩個遍歷序列重建二叉樹?
14. 判斷二叉樹是否為完全二叉樹?
15.判斷二叉樹B是不是二叉樹A的子結(jié)構(gòu)?
16.二叉樹的鏡像?
17.判斷一個序列是否是二叉搜索樹的后序遍歷序列?
18.求二叉樹中和為某一值的路徑
代碼如下：?
二叉樹的基本組成：
public class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; }}測試主方法：
import java.util.*;/** * 二叉樹題目匯總 * * 1、前序、中序、后序遍歷二叉樹，preOrder1，preOrder2,inOrder1,inOrder2,postOrder1,postOrder2 * 2、層序遍歷二叉樹，levelOrder1,levelOrder2 * 3、獲得二叉樹的深度，getDepth * 4、獲得二叉樹的節(jié)點個數(shù)，getNodesNum * 5、判斷兩棵二叉樹是否為相同的二叉樹，isSameTree * 6、判斷二叉樹是否為平衡二叉樹，isAVL * 7、獲得二叉樹的葉子節(jié)點個數(shù)，getLeafNodeNum * 8、獲得二叉樹第K層上的節(jié)點個數(shù)，getKthLevelNodesNum * 9、將二叉查找樹變?yōu)橛行虻碾p向鏈表，convertBST2DLL * 10、求二叉樹中兩個節(jié)點的最低公共祖先節(jié)點，getLastCommonParent * 11、求二叉樹兩個節(jié)點之間的最大距離，getMaxDistance * 12、求從根節(jié)點出發(fā)到node的路徑path,getNodePath * 13、根據(jù)兩個遍歷序列重建二叉樹，rebuildBinaryTreeByPreAndIn,rebuildBinaryTreeByInAndPost * 14、判斷二叉樹是否為完全二叉樹，isCompleteBinaryTree */@SuppressWarnings("All")public class TreeDemo { /* 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;// preOrder1(r1);// System.out.println("前序遍歷，遞歸");// preOrder2(r1);// System.out.println("前序遍歷，迭代");//// inOrder1(r1);// System.out.println("中序遍歷，遞歸");// inOrder2(r1);// System.out.println("中序遍歷，迭代");// postOrder1(r1);// System.out.println("后序遍歷，遞歸");// postOrder2(r1);// System.out.println("后序遍歷，迭代");// levelOrder1(r1);// System.out.println("層序遍歷，迭代");// levelOrder2(r1);// System.out.println("層序遍歷， 遞歸");// System.out.println(getDepth1(r1));// System.out.println(getDepth2(r1)); System.out.println(getNodesNum1(r1)); System.out.println(getNodesNum2(r1)); }}以下分別是前序，中序，后序遍歷二叉樹的遞歸和迭代解法，具體思路在方法前有說明。
/** * 前序遍歷，遞歸解法 * （1）如果二叉樹為空，空操作 * （2）如果二叉樹不為空，訪問根節(jié)點，前序遍歷左子樹，前序遍歷右子樹 */ public static void preOrder1(TreeNode root) { if(root == null) { return; } System.out.print(root.val " "); preOrder1(root.left); preOrder1(root.right); }/** * 前序遍歷，迭代 * 用一個輔助stack，總是把右孩子放進棧 */ public static void preOrder2(TreeNode root) { if(root == null) { return; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); //出棧頂元素 System.out.print(cur.val " "); // 關(guān)鍵點：要先壓入右孩子，再壓入左孩子，這樣在出棧時會先打印左孩子再打印右孩子 if(cur.right != null) { stack.push(cur.right); } if(cur.left != null) { stack.push(cur.left); } } }?
/** * 中序遍歷，遞歸 */ public static void inOrder1(TreeNode root) { if(root == null) { return; } inOrder1(root.left); System.out.print(root.val " "); inOrder1(root.right); }?
/** * 中序遍歷迭代解法 ，用棧先把根節(jié)點的所有左孩子都添加到棧內(nèi)， * 然后輸出棧頂元素，再處理棧頂元素的右子樹 * http://www.youtube.com/watch?v=50v1sJkjxoc * * 還有一種方法能不用遞歸和棧，基于線索二叉樹的方法，較麻煩以后補上 * http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/ */ public static void inOrder2(TreeNode root) { if(root == null) { return; } Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (true) { while (cur != null) { // 先添加一個非空節(jié)點所有的左孩子到棧 stack.push(cur); cur = cur.left; } if(stack.isEmpty()) { break; } // 因為此時已經(jīng)沒有左孩子了，所以輸出棧頂元素 cur = stack.pop(); System.out.print(cur.val " "); cur = cur.right; } }?
/** * 后序遍歷，遞歸 */ public static void postOrder1(TreeNode root) { if(root == null) { return; } postOrder1(root.left); postOrder1(root.right); System.out.print(root.val " "); } /** * 后序遍歷，迭代 * 需要用到兩個棧，分別將左子樹和右子樹壓入棧1，再取出第一個棧中的元素存放到棧2中，完成后序遍歷的逆序輸出 * @param root */ public static void postOrder2(TreeNode root) { if(root == null) { return; } Stack<TreeNode> stack = new Stack<>(); Stack<TreeNode> out = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); out.push(cur); if(cur.left != null) { stack.push(cur.left); } if(cur.right != null) { stack.push(cur.right); } } while (!out.isEmpty()) { System.out.print(out.pop().val " "); } }分別采用迭代和遞歸的方法來分層遍歷二叉樹
/** * 分層遍歷二叉樹（按層次從上往下，從左往右）迭代 * 相當(dāng)于廣度優(yōu)先搜索，使用隊列實現(xiàn)。隊列初始化，將根節(jié)點壓入隊列。當(dāng)隊列不為空，進行如下操作：彈出一個節(jié)點 */ public static void levelOrder1(TreeNode root) { if(root == null) { return; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(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有關(guān)系 * * 這是我目前見到的最好的遞歸解法！ * http://discuss.leetcode.com/questions/49/binary-tree-level-order-traversal#answer-container-2543 */ public static void levelOrder2(TreeNode root) { ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>(); dfs(root, 0, ret); System.out.print(ret); } public static void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> ret) { if(root == null) { return; } if(level >= ret.size()) { ret.add(new ArrayList<Integer>()); } ret.get(level).add(root.val); //把節(jié)點值加入到表示那一層的list集合中 dfs(root.left, level 1, ret); dfs(root.right, level 1, ret); }獲得二叉樹深度的遞歸和迭代解法：
/** * 求二叉樹的深度（高度） 遞歸解法： O(n) * （1）如果二叉樹為空，二叉樹的深度為0 * （2）如果二叉樹不為空，二叉樹的深度 = max(左子樹深度， 右子樹深度) 1 */ public static int getDepth1(TreeNode root) { if(root == null) { return 0; } int left = getDepth1(root.left); int right = getDepth1(root.right); return Math.max(left, right) 1; } /** * 求二叉樹的深度（高度） 迭代解法： O(n) * 基本思想同LevelOrder，還是用一個Queue */ public static int getDepth2(TreeNode root) { if(root == null) { return 0; } int depth = 0; int currentLevelNodes = 1; //當(dāng)前層的節(jié)點數(shù) int nextLevelNodes = 0; //下一層的節(jié)點數(shù) LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode cur = queue.removeFirst(); //從隊頭位置開始移除 currentLevelNodes--; //當(dāng)前層數(shù)節(jié)點減1 if(cur.left != null) { //當(dāng)前節(jié)點有左子節(jié)點，加入隊列中 queue.add(cur.left); nextLevelNodes ; //并將下一層節(jié)點數(shù)加1 } if(cur.right != null) { queue.add(cur.right); nextLevelNodes ; } if(currentLevelNodes == 0) { //如果處理完當(dāng)前層的所有節(jié)點 depth ; //深度加1 currentLevelNodes = nextLevelNodes; //初始化當(dāng)前層為下一層 nextLevelNodes = 0; } } return depth; }遞歸：
/** * 二叉樹的節(jié)點個數(shù)，遞歸 */ public static int getNodesNum1(TreeNode root) { if(root == null) { return 0; } int left = getNodesNum1(root.left); int right = getNodesNum1(root.right); return left right 1; } /** * 二叉樹的節(jié)點個數(shù)，迭代 * java用LinkedList來模擬queue的用法 */ public static int getNodesNum2(TreeNode root) { if(root == null) { return 0; } int count = 1; LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode cur = queue.removeFirst(); if(cur.left != null) { queue.add(cur.left); count ; } if(cur.right != null) { queue.add(cur.right); count ; } } return count; } /** * 判斷兩顆二叉樹是否為相同的二叉樹,遞歸 */ public static boolean isSameTree1(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 left = isSameTree1(r1.left, r2.left); //分別比較左子樹和右子樹是否相等 boolean right = isSameTree1(r1.right, r2.right); return left && right; } /** * 判斷兩顆二叉樹是否相同，迭代解法 * 分別用兩個棧來存儲兩棵樹，采用前序遍歷的方法依次比較兩顆二叉樹的各個節(jié)點的值是否相等， * 如果不相等直接返回空，相等就繼續(xù)將后面的節(jié)點入棧 */ public static boolean isSameTree2(TreeNode r1, TreeNode r2) { if(r1 == null && r2 == null) { return true; } else if(r1 == null || r2 == null) { return false; } Stack<TreeNode> s1 = new Stack<>(); Stack<TreeNode> s2 = new Stack<>(); s1.add(r1); s2.add(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 isAVL(TreeNode root) { if(root == null) { return true; } if(Math.abs(getDepth1(root.left) - getDepth1(root.right)) > 1) { return false; } return isAVL(root.left) && isAVL(root.right); } /** * 求二叉樹中葉子節(jié)點的個數(shù)，遞歸 */ public static int getLeafNodeNum1(TreeNode root) { if(root == null) { return 0; } if(root.left == null && root.right == null) { return 1; } return getLeafNodeNum1(root.left) getLeafNodeNum1(root.right); } /** * 求二叉樹中葉子節(jié)點的個數(shù)，迭代 * 基于層序遍歷的思想 */ public static int getLeafNodeNum2(TreeNode root) { if(root == null) { return 0; } int count = 0; LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode cur = queue.removeFirst(); if(cur.left == null && cur.right == null) { count ; } if(cur.left != null) { queue.add(cur.left); } if(cur.right != null) { queue.add(cur.right); } } return count; } /** * 求二叉樹第K層節(jié)點的個數(shù) * （1）如果二叉樹為空或者k<1返回0 * （2）如果二叉樹不為空并且k==1，返回1 * （3）如果二叉樹不為空且k>1，返回root左子樹中k-1層的節(jié)點個數(shù)與root右子樹k-1層節(jié)點個數(shù)之和 * * 求以root為根的k層節(jié)點數(shù)目 等價于 求以root左孩子為根的k-1層（因為少了root那一層）節(jié)點數(shù)目 加上 * 以root右孩子為根的k-1層（因為少了root那一層）節(jié)點數(shù)目 * * 所以遇到樹，先把它拆成左子樹和右子樹，把問題降解 */ public static int getKthLevelNodesNum1(TreeNode root, int k) { if(root == null || k < 1) { return 0; } if(k == 1) { return 1; } int left = getKthLevelNodesNum1(root.left, k-1); //求root左子樹的k-1層節(jié)點數(shù) int right = getKthLevelNodesNum1(root.right, k-1); return left right; } /** * 求二叉樹第K層節(jié)點數(shù)目，迭代 * 利用層序遍歷的思想 */ public static int getKthLevelNodesNum2(TreeNode root, int k) { if(root == null || k < 1) { return 0; } if(k == 1) { return 1; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); int currentLevelNodes = 1; int nextLevelNodes = 0; int i = 1; while (!queue.isEmpty() && i < k) { TreeNode cur = queue.removeFirst(); //移除隊頭位置 currentLevelNodes--; //當(dāng)前層節(jié)點數(shù)減1 if(cur.left != null) { queue.add(cur.left); nextLevelNodes ; } if(cur.right != null) { queue.add(cur.right); nextLevelNodes ; } if(currentLevelNodes == 0) { currentLevelNodes = nextLevelNodes; nextLevelNodes = 0; i ; } } return currentLevelNodes; } /** * 將二叉查找樹變?yōu)橛行虻碾p向鏈表 要求不能創(chuàng)建新節(jié)點，只調(diào)整指針。 * 節(jié)點的左即為鏈表前一節(jié)點，右即為鏈表后一節(jié)點 * 遞歸解法： * 參考了http://stackoverflow.com/questions/11511898/converting-a-binary-search-tree-to-doubly-linked-list#answer-11530016 * 感覺是最清晰的遞歸解法，但要注意遞歸完，root會在鏈表的中間位置，因此要手動 * 把root移到鏈表頭或鏈表尾 */ public static TreeNode convertBST2DLL1(TreeNode root) { root = convertBST2DLLSub(root); // root會在鏈表的中間位置，因此要手動把root移到鏈表頭 while (root.left != null) { root = root.left; } return root; } /** * 遞歸轉(zhuǎn)換二叉查找樹為雙向鏈表(DLL) */ public static TreeNode convertBST2DLLSub(TreeNode root) { if(root == null || (root.left == null && root.right == null)) { return root; } TreeNode tmp = null; if(root.left != null) { //處理左子樹 tmp = convertBST2DLLSub(root.left); while (tmp.right != null) { //尋找最右節(jié)點 tmp = tmp.right; } tmp.right = root; //把左子樹處理后結(jié)果和root連接 root.left = tmp; } if(root.right != null) { //處理右子樹 tmp = convertBST2DLLSub(root.right); while (tmp.left != null) { //尋找最左節(jié)點 tmp = tmp.left; } tmp.left = root; //把右子樹處理后結(jié)果和root連接 root.right = tmp; } return root; } /** * 二叉查找樹轉(zhuǎn)換為雙向鏈表，迭代解法 * 基本思想同中序遍歷二叉樹 */ public static TreeNode convertBST2DLL2(TreeNode root) { if(root == null) { return null; } Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; //指向當(dāng)前正在處理的節(jié)點 TreeNode old = null; //前一節(jié)點 TreeNode head = null; //雙向鏈表的頭結(jié)點 while (true) { while (cur != null) { //將所有左節(jié)點全部入棧 stack.push(cur); cur = cur.left; } if(stack.isEmpty()) { break; } //由于此時沒有左孩子了，所以輸出棧頂元素 cur = stack.pop(); if(old != null) { old.right = cur; } if(head == null) { //第一個結(jié)點為雙向鏈表頭結(jié)點 head = cur; } old = cur; //更新old cur = cur.right; //準(zhǔn)備處理右子樹 } return head; } /** * 求二叉樹中兩個節(jié)點的最低公共祖先節(jié)點 * 遞歸解法： * （1）如果兩個節(jié)點分別在根節(jié)點的左子樹和右子樹，則返回根節(jié)點 * （2）如果兩個節(jié)點都在左子樹，則遞歸處理左子樹；如果兩個節(jié)點都在右子樹，則遞歸處理右子樹 */ public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2) { if(findNode(root.left, n1)) { //如果節(jié)點n1在樹的左子樹 if(findNode(root.right, n2)) { //節(jié)點n2在樹的右子樹 return root; } else { //節(jié)點n2也在左子樹，則遞歸處理左子樹 return getLastCommonParent(root.left, n1, n2); } } else { //n1在右子樹 if(findNode(root.left, n2)) { return root; } else { return getLastCommonParent(root.right, n1, n2); } } } //遞歸判斷一個節(jié)點是否在樹里 public static boolean findNode(TreeNode root, TreeNode n) { if(root == null || n == null) { return false; } if(root == n) { return true; } //先嘗試在左子樹里查找 boolean found = findNode(root.left, n); if(!found) { //如果不在左子樹中 found = findNode(root.right, n); //在右子樹中查找 } return found; } //求二叉樹中兩個節(jié)點的最低公共祖先節(jié)點，更加簡便的遞歸方法 public static TreeNode getLastCommonParent1(TreeNode root, TreeNode n1, TreeNode n2) { if(root == null) { return null; } //如果兩者有一個與root 相同 if(root.equals(n1) || root.equals(n2)) { return root; } TreeNode commonInLeft = getLastCommonParent1(root.left, n1, n2); TreeNode commonInRight = getLastCommonParent1(root.right, n1, n2); //如果一個在左子樹找到一個在右子樹找到，則為root if(commonInLeft != null && commonInRight != null) { return root; } //其他情況要不然在左子樹要不然在右子樹 if(commonInLeft != null) { return commonInLeft; } return commonInRight; }/** * 獲取兩個節(jié)點的最低公共祖先節(jié)點，復(fù)雜度比較低，也是面試官想看到的解法 * 算法思路： * 1）分別獲得一條從根節(jié)點到指定節(jié)點的路徑，該過程需要輔助空間List來存放路徑上的節(jié)點 * 2）求這兩條路徑的最后一個橡膠的節(jié)點即為題目想要找到的節(jié)點 * 得到兩條路在最壞情況下的時間復(fù)雜度是O(n),通常情況下兩條路徑的長度是O(logn) */ public static TreeNode getLastCommonParent2(TreeNode root, TreeNode n1, TreeNode n2) { if(root == null || n1 == null || n2 == null) { return null; } ArrayList<TreeNode> path1 = new ArrayList<>(); getNodePath(root, n1, path1); ArrayList<TreeNode> path2 = new ArrayList<>(); getNodePath(root, n2, path2); return getCommonNode(path1, path2); } //獲得兩條路徑的最后一個公共節(jié)點 public static TreeNode getCommonNode(List<TreeNode> path1, List<TreeNode> path2) { int i = 0; TreeNode res = null; while (i < path1.size() && i < path2.size()) { if(path1.get(i) == path2.get(i)) { res = path1.get(i); i ; } else { break; } } return res; } /** * 求二叉樹中節(jié)點的最大距離 即二叉樹中相距最遠的兩個節(jié)點之間的距離。 (distance / diameter) * 遞歸解法： * （1）如果二叉樹為空，返回0，同時記錄左子樹和右子樹的深度，都為0 * （2）如果二叉樹不為空，最大距離要么是左子樹中的最大距離，要么是右子樹中的最大距離， * 要么是左子樹節(jié)點中到根節(jié)點的最大距離 右子樹節(jié)點中到根節(jié)點的最大距離， * * 同時記錄左子樹和右子樹節(jié)點中到根節(jié)點的最大距離。 * * http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html * * 計算一個二叉樹的最大距離有兩個情況: 情況A: 路徑經(jīng)過左子樹的最深節(jié)點，通過根節(jié)點，再到右子樹的最深節(jié)點。 情況B: 路徑不穿過根節(jié)點，而是左子樹或右子樹的最大距離路徑，取其大者。 只需要計算這兩個情況的路徑距離，并取其大者，就是該二叉樹的最大距離 */ public static Result getMaxDistance(TreeNode root) { if(root == null) { Result empty = new Result(0, -1); // 目的是讓調(diào)用方 1 后，把當(dāng)前的不存在的 (NULL) 子樹當(dāng)成最大深度為 0 return empty; } //計算出左右子樹分別最大距離 Result lmd = getMaxDistance(root.left); Result rmd = getMaxDistance(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; } } /** * 把從根節(jié)點出發(fā)到node節(jié)點的路徑所有經(jīng)過的節(jié)點添加到路徑path中 */ public static boolean getNodePath(TreeNode root, TreeNode node, ArrayList<TreeNode> path) { if(root == null) { return false; } path.add(root); //先將根節(jié)點添加到路徑中 if(root == node) { return true; } boolean found = getNodePath(root.left, node, path); //在左子樹中找node節(jié)點 if(!found) { //左子樹中沒有node節(jié)點，在右子樹中查找 found = getNodePath(root.right, node, path); } if(!found) { //如果左右子樹中都不存在node節(jié)點，則將之前加到path中的root節(jié)點刪除 path.remove(root); } return found; } /** * 根據(jù)前序遍歷序列和中序遍歷序列重建二叉樹 */ public static TreeNode rebuildBinaryTreeByPreAndIn(List<TreeNode> preOrder, List<TreeNode> inOrder) { TreeNode root = null; //定義二叉樹根節(jié)點 List<TreeNode> leftPreOrder; //左子樹前序遍歷序列 List<TreeNode> rightPreOrder; //右子樹前序遍歷序列 List<TreeNode> leftInOrder; //左子樹中序遍歷序列 List<TreeNode> rightInOrder; //右子樹中序遍歷序列 int preNum = 0; int inNum = 0; if((!preOrder.isEmpty()) && (!inOrder.isEmpty())) { root = preOrder.get(0); //前序遍歷的第一個節(jié)點即為根節(jié)點 //根據(jù)root的位置，可以確定inOrder左邊的是左子樹序列，右邊的是右子樹序列 inNum = inOrder.indexOf(root); //找到root在inOrder中的位置 leftInOrder = inOrder.subList(0, inNum); //左子樹中序遍歷序列 rightInOrder = inOrder.subList(inNum 1, inOrder.size()); //右子樹中序遍歷序列 preNum = leftInOrder.size(); //前序序列的分割點 leftPreOrder = preOrder.subList(1, preNum 1); rightPreOrder = preOrder.subList(preNum 1, preOrder.size()); root.left = rebuildBinaryTreeByPreAndIn(leftPreOrder, leftInOrder); // root的左子樹就是preorder和inorder的左側(cè)區(qū)間而形成的樹 root.right = rebuildBinaryTreeByPreAndIn(rightPreOrder, rightInOrder); } return root; } /** * 根據(jù)中序和后序遍歷序列重建二叉樹 */ public static TreeNode rebuildBinaryTreeByInAndPost(List<TreeNode> inOrder, List<TreeNode> postOrder) { TreeNode root = null; //新建根節(jié)點 List<TreeNode> leftInOrder; List<TreeNode> rightInOrder; List<TreeNode> leftPostOrder; List<TreeNode> rightPostOrder; int inNum = 0; int postNum = 0; if((inOrder.size() != 0) && (postOrder.size() != 0)) { root = postOrder.get(postOrder.size()-1); //后序遍歷序列的最后一個節(jié)點即為根節(jié)點 //由root節(jié)點的位置可以分割中序遍歷序列 inNum = inOrder.indexOf(root); leftInOrder = inOrder.subList(0, inNum); rightInOrder = inOrder.subList(inNum 1, inOrder.size()); postNum = leftInOrder.size(); //后序遍歷序列的左右子樹分割點 leftPostOrder = postOrder.subList(0, postNum); rightPostOrder = postOrder.subList(postNum, postOrder.size()); root.left = rebuildBinaryTreeByInAndPost(leftInOrder, leftPostOrder); root.right = rebuildBinaryTreeByInAndPost(rightInOrder, rightPostOrder); } return root; } /** * 判斷二叉樹是否為完全二叉樹，迭代 * 若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達到最大個數(shù)， 第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。 有如下算法，按層次（從上到下，從左到右）遍歷二叉樹，當(dāng)遇到一個節(jié)點的左子樹為空時， 則該節(jié)點右子樹必須為空，且后面遍歷的節(jié)點左右子樹都必須為空，否則不是完全二叉樹。 */ public static boolean isCompleteBinaryTree1(TreeNode root) { if(root == null) { return false; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); boolean mastHaveNoChild = false; boolean result = false; while (!queue.isEmpty()) { TreeNode cur = queue.remove(); //隊列先進先出 if(mastHaveNoChild){ // 已經(jīng)出現(xiàn)了有空子樹的節(jié)點了，后面出現(xiàn)的必須為葉節(jié)點（左右子樹都為空） if(cur.left != null || cur.right != null) { result = false; break; } } else { if(cur.left == null && cur.right != null) { //如果左子樹為空，右子樹非空則說明不是完全二叉樹 result = false; break; } else if(cur.left != null && cur.right == null) { //如果左子樹非空，右子樹為空，則左子節(jié)點不能有左右子樹 mastHaveNoChild = true; queue.add(cur.left); } else if(cur.left != null && cur.right != null) { //如果左右子孩子都非空，則加入隊列繼續(xù)循環(huán) queue.add(cur.left); queue.add(cur.right); } else { // 如果左右子樹都為空，則后面的必須也都為空子樹 mastHaveNoChild = true; } } } return result; } /** * 判斷二叉樹是否是完全二叉樹，遞歸解法 */ public static boolean isCompleteBinaryTree2(TreeNode root) { return isCompleteTree(root).height != -1; } public static Pair isCompleteTree(TreeNode root) { if(root == null) { return new Pair(0, true); } Pair left = isCompleteTree(root.left); Pair right = isCompleteTree(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(left.height 1, false); } //其他情況都不是完全二叉樹 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; } } /** * 兩顆二叉樹A,B，判斷B是不是A的子樹 * * 解題思路： * 1）在樹A中找到樹B的根節(jié)點值一樣的節(jié)點R * 2）判斷A中以R為根節(jié)點的子樹是不是包含和樹B一樣的結(jié)構(gòu) */ public static boolean isSubTree(TreeNode root1, TreeNode root2) { boolean result = false; if(root1 != null && root2 != null) { //兩顆二叉樹都不為空的時候 //如果在A中找到和B的根節(jié)點值相同的節(jié)點R，則調(diào)用doseTree1HasTree2做第二步判斷 if(root1.val == root2.val) { result = doseTree1HasTree2(root1, root2); } //如果在A中沒有找到和B的根節(jié)點相同的節(jié)點R，則遞歸遍歷左右子樹尋找 if(!result) { result = isSubTree(root1.left, root2); } if(!result) { result = isSubTree(root1.right, root2); } } return result; } //第二步，判斷A中以R為根節(jié)點的子樹是不是和樹B有相同的結(jié)構(gòu) public static boolean doseTree1HasTree2(TreeNode root1, TreeNode root2) { //這里一定是root2的判斷在前，若先判斷root1則可能會出現(xiàn)root1和root2都為空的情況，此時返回的是false答案將會是錯誤的，所以一定要先判斷root2 if(root2 == null) { return true; } if(root1 == null) { return false; } if(root1.val != root2.val) { return false; } //遞歸判斷他們左右子節(jié)點的值是否相同 return doseTree1HasTree2(root1.left, root2.left) && doseTree1HasTree2(root1.right, root2.right); } /** * 求一棵二叉樹的鏡像 * * 解題過程：（遞歸） * 先前序遍歷這棵樹的每個節(jié)點，如果遍歷到的節(jié)點有子節(jié)點，則交換兩個子節(jié)點（同時也是交換了它的左右子樹）， * 當(dāng)交換完所有非葉子結(jié)點的子節(jié)點以后，就得到了樹的鏡像 * 該解法會破壞原二叉樹的結(jié)構(gòu) */ public static void mirrorTree(TreeNode root) { //如果該樹為空樹或者是只有一個節(jié)點的樹，則直接返回 if(root == null || (root.left == null && root.right == null)) { return; } //交換左右子節(jié)點 TreeNode temp = root.left; root.left = root.right; root.right = temp; if(root.left != null) { //如果左子節(jié)點存在 //遞歸遍歷左子樹 mirrorTree(root.left); } if(root.right != null) { mirrorTree(root.right); } } /** * 求一棵二叉樹的鏡像 * * 迭代解法 * 仍然采用前序遍歷的方法，用棧來實現(xiàn) */ public static void mirrorTree2(TreeNode root) { if(root == null) { return; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); TreeNode temp = cur.left; cur.left = cur.right; cur.right = temp; if(cur.right != null) { //前序遍歷，先壓入右節(jié)點，再壓入左節(jié)點 stack.push(cur.right); } if(cur.left != null) { stack.push(cur.left); } } }?
//不改變原二叉樹的迭代解法 public static TreeNode mirrorTree3(TreeNode root) { if(root == null) { return null; } TreeNode newRoot = new TreeNode(root.val); Stack<TreeNode> stack = new Stack<>(); Stack<TreeNode> newStack = new Stack<>(); stack.push(root); 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; } /** * 判斷一個序列是否是二叉搜索樹的后序遍歷序列 * * 根據(jù)后序遍歷序列的規(guī)則，最后一個元素即根元素，比根元素小的是左子樹，大的是右子樹，然后遞歸判斷 * * @param start 起始索引下標(biāo) * @param end 結(jié)束索引下標(biāo) */ public static boolean verifySequenceOfBST(int[] sequence, int start, int end) { if(sequence == null || start < 0 || end <= 0) { return false; } int root = sequence[end]; //根節(jié)點就是最后一個元素 //在二叉搜索樹中左子樹的節(jié)點都比右子樹小 int i = 0; for (; i < end; i ) { if(sequence[i] > root) { break; } } //在二叉搜索樹中右子樹的節(jié)點大于根節(jié)點 int j = i; //右子樹的第一個元素（序列中的元素） for (; j < end; j ) { if(sequence[j] < root) { return false; } } //判斷左子樹是不是二叉搜索樹 boolean left = true; i--; if(i > 0) { left = verifySequenceOfBST(sequence, 0, i); } //判斷右子樹是不是二叉搜索樹 boolean right = true; i ; if(i < end) { right = verifySequenceOfBST(sequence, i, end-1); } return (left && right); } /** * 求二叉樹中和為某一值的路徑 * 題目描述：從樹的根節(jié)點開始往下一直到葉節(jié)點所經(jīng)過的節(jié)點形成一條路徑 * * 解題思路： * 用前序遍歷的方式訪問某一節(jié)點時，把該節(jié)點加入到路徑上，并且累加該節(jié)點的值。 * 如果該節(jié)點為葉子節(jié)點并且路徑中節(jié)點值的和剛好等于輸入的整數(shù)，則當(dāng)前路徑符合要求，可以打印出來； * 如果當(dāng)前節(jié)點不是葉子節(jié)點，則繼續(xù)訪問它的子節(jié)點。 * 當(dāng)前節(jié)點訪問結(jié)束后，遞歸函數(shù)自動回到它的父節(jié)點。（實際可以用棧來滿足） * 因此在退出之前要在路徑上刪除當(dāng)前節(jié)點，并且減去當(dāng)前節(jié)點的值，以確保返回父節(jié)點時路徑剛好是從根節(jié)點到父節(jié)點的路徑 */ public static void findPath(TreeNode root, int sum) { if(root == null) { return; } int currentSum = 0; //用java里面LinkedList的add和removeLast方法實現(xiàn)棧的先進后出特性，這樣方便和面打印路徑 LinkedList<Integer> path = new LinkedList<>(); //用于存儲路徑 findPathTemp(root, sum, path, currentSum); } public static void findPathTemp(TreeNode root, int sum, LinkedList<Integer> path, int currentSum) { currentSum = root.val; path.addLast(root.val); //如果是葉子節(jié)點，并且路徑上節(jié)點值的和等于輸入的整數(shù) boolean isLeaf = false; if(root.left == null && root.right == null) { isLeaf = true; } if(currentSum == sum && isLeaf) { System.out.println("A path is found:"); for (int i = 0; i < path.size(); i ) { System.out.printf("%d\t", path.get(i)); } System.out.println(); } //如果不是葉子節(jié)點，則遍歷它的子節(jié)點 if(root.left != null) { findPathTemp(root.left, sum, path, currentSum); } if(root.right != null) { findPathTemp(root.right, sum, path, currentSum); } //在返回父節(jié)點之前，在路徑上刪除當(dāng)前節(jié)點 path.removeLast(); }