目錄

1. 題目1：檢查兩棵樹是否相同

?2. 題目2：判斷一棵樹是否為另一棵樹的子樹

3. 題目3：翻轉(zhuǎn)二叉樹

4. 題目4：判斷一棵樹是否為平衡二叉樹

5. 題目5：判斷一棵樹是否為對稱二叉樹

6. 題目6：二叉樹的層序遍歷

7. 題目7：二叉樹的遍歷

8. 題目8：二叉樹的最近公共祖先

9. 題目9：根據(jù)前序與中序遍歷構(gòu)造二叉樹

10. 題目10：根據(jù)中序與后序遍歷構(gòu)造二叉樹

11. 題目11：根據(jù)二叉樹創(chuàng)建字符串

12. 題目12：非遞歸實現(xiàn)二叉樹前序遍歷

13. 題目13：非遞歸實現(xiàn)二叉樹中序遍歷

14. 題目14：非遞歸實現(xiàn)二叉樹后序遍歷

---

1. 題目1：檢查兩棵樹是否相同

題目鏈接：100. 相同的樹 - 力扣（LeetCode）

解題思路：遞歸思路：判斷根節(jié)點是否相同，左子樹是否相同，右子樹是否相同；

相同判定有兩方面：結(jié)構(gòu)與數(shù)值；

代碼：

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {// 兩樹均為空if(p == null && q == null){return true;}// 兩樹一空一非空if((p == null && q != null)||(p != null && q == null)){return false;}// 兩樹均不為空// 兩樹根節(jié)點數(shù)據(jù)域值不同if(p.val != q.val){return false;}// 兩樹根節(jié)點數(shù)據(jù)域值相同return isSameTree(p.left,q.left) && isSameTree(p.right, q.right);}
}

時間復(fù)雜度：O(min(m,n))；其中mn分別為兩棵樹的結(jié)點數(shù)；

?2. 題目2：判斷一棵樹是否為另一棵樹的子樹

題目鏈接：572. 另一棵樹的子樹 - 力扣（LeetCode）

解題思路：判斷兩棵樹是否相同，遞歸判斷一棵是否為另一棵的左子樹，是否為其右子樹；

代碼：

class Solution {public boolean isSameTree(TreeNode p, TreeNode q){if(p == null && q == null){return true;}if((p == null && q != null) || (p != null && q == null)){return false;}if(p.val != q.val){return false;}return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null || subRoot == null){return false;}if(isSameTree(root, subRoot)){return true;}if(isSubtree(root.left,subRoot)){return true;}if(isSubtree(root.right, subRoot)){return true;}return false;}
}

時間復(fù)雜度：O(s * t)；

3. 題目3：翻轉(zhuǎn)二叉樹

題目鏈接：226. 翻轉(zhuǎn)二叉樹 - 力扣（LeetCode）

解題思路：在二叉樹不為空時，將二叉樹的左右子樹交換，再遞歸交換左子樹的左右子樹和右子樹的左右子樹；

代碼：

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null){return null;}TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;}
}

4. 題目4：判斷一棵樹是否為平衡二叉樹

題目鏈接：110. 平衡二叉樹 - 力扣（LeetCode）

解題思路：

代碼1：

class Solution {public boolean isBalanced(TreeNode root) {if(root == null){return true;}int leftH = maxDepth(root.left);int rightH = maxDepth(root.right);return  Math.abs(leftH - rightH) <2&& isBalanced(root.left) && isBalanced(root.right);}public int maxDepth(TreeNode root){if(root == null){return 0;}int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return (leftHeight>rightHeight)?(leftHeight+1):(rightHeight+1);}
}

時間復(fù)雜度：O(N2)；

代碼2：

class Solution {public boolean isBalanced(TreeNode root) {return maxDepth(root) >=0;}public int maxDepth(TreeNode root){if(root == null){return 0;}int leftHeight = maxDepth(root.left);if(leftHeight < 0){return -1;}int rightHeight = maxDepth(root.right);if(rightHeight < 0){return -1;}if(Math.abs(leftHeight - rightHeight) <= 1){return Math.max(leftHeight,rightHeight)+1;}else{return -1;}}
}

時間復(fù)雜度：O（N）；

5. 題目5：判斷一棵樹是否為對稱二叉樹

題目鏈接：101. 對稱二叉樹 - 力扣（LeetCode）

代碼：

class Solution {public boolean isSymmetric(TreeNode root) {if(root == null){return true;}// 判斷左子樹的左樹 和 右子樹的右樹是否對稱return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree){if(leftTree == null && rightTree == null){return true;}if((leftTree == null && rightTree != null)||(leftTree != null && rightTree == null)){return false;}// 左右子樹均不為空// 左右子樹根節(jié)點數(shù)據(jù)不同if(leftTree.val != rightTree.val){return false;}// 左右子樹根節(jié)點數(shù)據(jù)相同return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);}
}

6. 題目6：二叉樹的層序遍歷

題目鏈接：102. 二叉樹的層序遍歷 - 力扣（LeetCode）

代碼：

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<>();if(root == null){return list;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int size = queue.size();List<Integer> tmp = new ArrayList<>();while(size != 0){TreeNode cur = queue.poll();tmp.add(cur.val);size--;if(cur.left != null){queue.offer(cur.left);}if(cur.right != null){queue.offer(cur.right);}}list.add(tmp);}return list;}
}

7. 題目7：二叉樹的遍歷

題目鏈接：二叉樹遍歷_?？皖}霸_?？途W(wǎng)

代碼：

import java.util.Scanner;
class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val = val;}
}
// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的區(qū)別while (in.hasNextLine()) { // 注意 while 處理多個 casei=0;  // 將i置為0，防止多組測試i累加String str = in.nextLine();TreeNode root = createTree(str);inOrder(root);}}public static int i = 0;public static TreeNode createTree(String str){TreeNode root = null;if(str.charAt(i)!='#'){// 遍歷字符串，不為空的字符創(chuàng)建結(jié)點：root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);}else{// 字符串遍歷至#：i++;}return root;}public static void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.val+" ");inOrder(root.right);}
}

8. 題目8：二叉樹的最近公共祖先

題目鏈接：236. 二叉樹的最近公共祖先 - 力扣（LeetCode）

解題思路：

方法1：除過空樹與pq二者之一為根結(jié)點的情況外，分為三種情況：第一種：pq分別在根的左右兩邊；第二種：pq都在根的左邊或右邊；第三種：pq中有一個結(jié)點是公共祖先；

代碼：

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){if(root == null){return null;}if(p == root || q == root){return root;}// 分別在根結(jié)點的左右子樹查找目標(biāo)結(jié)點TreeNode leftRet = lowestCommonAncestor(root.left, p, q);TreeNode rightRet = lowestCommonAncestor(root.right, p, q);// 第一種情況：左右子樹均有目標(biāo)結(jié)點則根結(jié)點為公共祖先if(leftRet != null && rightRet != null){return root;}else if(leftRet != null){// 第二種情況： 右子樹沒有查詢到目標(biāo)結(jié)點：兩個目標(biāo)結(jié)點均在左子樹return leftRet;// leftRet已經(jīng)記錄了左子樹查詢到的第一個目標(biāo)結(jié)點// 同時由于2個目標(biāo)結(jié)點均在左子樹，即已經(jīng)記錄到的leftRet即是兩個結(jié)點的最近公共祖先}else if(rightRet != null){// 左子樹沒有查詢到目標(biāo)結(jié)點：兩個目標(biāo)結(jié)點均在右子樹return rightRet;// 同第一個else-if語句，rightRet即是2個目標(biāo)結(jié)點的最近公共祖先}return null;}

方法2：建兩個棧，分別存儲pq兩結(jié)點從根結(jié)點開始途徑的每一個結(jié)點，從結(jié)點多的棧開始出棧，從兩個棧元素數(shù)量相同開始，兩個棧同時彈出棧頂元素進行比較是否相同，相同則是公共祖先，不相同則依次比較下一個元素；

代碼：

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 建2個棧分別用于存放根結(jié)點root到目標(biāo)結(jié)點p與q的路徑結(jié)點Deque<TreeNode> stack1 = new LinkedList<>();getPath(root, p, stack1);Deque<TreeNode> stack2 = new LinkedList<>();getPath(root, q, stack2);// 判斷棧大小，先出棧元素多的棧直至與另一個棧元素個數(shù)相同，兩棧開始同時出棧元素int size1 = stack1.size();int size2 = stack2.size();if(size1> size2){int size = size1 - size2;while(size != 0){stack1.pop();size--;}}else{int size = size2 - size1;while(size != 0){stack2.pop();size--;}}// 此時兩棧元素個數(shù)已經(jīng)相同// 當(dāng)兩個棧均不為空時，逐個元素對比while(!stack1.isEmpty() && !stack2.isEmpty()){// 兩棧棧頂元素不同則同時出棧if(stack1.peek() != stack2.peek()){stack1.pop();stack2.pop();}else{// 兩棧棧頂元素相同：該結(jié)點為公共祖先return stack1.peek();}}return null;}public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack){// 查找從根結(jié)點root到目標(biāo)結(jié)點node路徑上的結(jié)點并存放到棧stack中if(root == null || node == null){return false;}// 將當(dāng)前結(jié)點入棧stack.push(root);// 判斷該結(jié)點是否為目標(biāo)結(jié)點if(root == node){return true;}// 判斷該結(jié)點左子樹中是否有目標(biāo)結(jié)點boolean ret1 = getPath(root.left, node, stack);if(ret1 == true){return true;}// 判斷該結(jié)點右子樹中是否有目標(biāo)結(jié)點boolean ret2 = getPath(root.right, node, stack);if(ret2 == true){return true;}// 左右子樹均查詢無果，則出棧該結(jié)點并返回空stack.pop();return false;}
}

注：如果二叉樹每個結(jié)點中存儲了其父親結(jié)點的地址，則改題等效于求兩個鏈表的交叉結(jié)點問題；

9. 題目9：根據(jù)前序與中序遍歷構(gòu)造二叉樹

題目鏈接：105. 從前序與中序遍歷序列構(gòu)造二叉樹 - 力扣（LeetCode）

代碼：

class Solution {public int i=0;  //用于前序preorder遍歷public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder, inorder, 0,inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBgein, int inEnd){if(inBgein > inEnd){   // 沒有子樹return null;}TreeNode root = new TreeNode(preorder[i]);  // root結(jié)點// 在中序遍歷inorder中定位根結(jié)點root位置int rootIndex = findIndex(inorder, inBgein, inEnd, preorder[i]);i++;// 在中序遍歷中確定根結(jié)點位置后，其左為左樹，右為右樹root.left = buildTreeChild(preorder, inorder, inBgein, rootIndex-1);root.right = buildTreeChild(preorder, inorder, rootIndex+1, inEnd);return root;}private int findIndex(int[] inorder, int inBgein, int inEnd, int key){for(int i=inBgein; i<= inEnd;i++){if(inorder[i] == key){return i;}}return -1;}
}

10. 題目10：根據(jù)中序與后序遍歷構(gòu)造二叉樹

題目鏈接：106. 從中序與后序遍歷序列構(gòu)造二叉樹 - 力扣（LeetCode）

代碼：

class Solution {public int i =0;public TreeNode buildTree(int[] inorder, int[] postorder) {i = inorder.length-1;return  buildTreeChild(postorder, inorder, 0, inorder.length-1);}public TreeNode buildTreeChild(int[] postorder, int[] inorder, int inBegin, int inEnd){if(inBegin > inEnd){return null;}TreeNode root = new TreeNode(postorder[i]);int rootIndex = findIndex(inorder, inBegin, inEnd, postorder[i]);i--;root.right = buildTreeChild(postorder, inorder, rootIndex+1, inEnd);root.left = buildTreeChild(postorder, inorder, inBegin, rootIndex-1);return root;}private int findIndex(int[] inorder, int inBegin, int inEnd, int key){for(int j=inBegin;j<=inEnd;j++){if(inorder[j] == key){return j;}}return -1;}
}

11. 題目11：根據(jù)二叉樹創(chuàng)建字符串

題目鏈接：606. 根據(jù)二叉樹創(chuàng)建字符串 - 力扣（LeetCode）

解題思路：分為以下三種情況：（1）結(jié)點左右均為空：直接返回；（2）結(jié)點左不為空右為空：無需為空結(jié)點增加括號；（3）結(jié)點左空右不為空，給空結(jié)點增加括號；

代碼：

class Solution {public String tree2str(TreeNode root) {if(root == null){return null;}StringBuilder stringBuilder = new StringBuilder();tree2strChild(root, stringBuilder);return stringBuilder.toString();}public void tree2strChild(TreeNode node, StringBuilder stringBuilder){if(node == null){return;}stringBuilder.append(node.val);// 判斷結(jié)點左子樹if(node.left != null){// 結(jié)點左孩子不為空stringBuilder.append("(");tree2strChild(node.left, stringBuilder);stringBuilder.append(")");}else{// 結(jié)點左孩子為空// 情況1：結(jié)點右孩子不為空if(node.right != null){stringBuilder.append("()");}else{// 情況2：結(jié)點右孩子為空return;}}// 判斷結(jié)點右子樹if(node.right == null){// 結(jié)點右孩子為空：直接返回return;}else{// 結(jié)點右孩子不為空：遞歸結(jié)點的右子樹stringBuilder.append("(");tree2strChild(node.right, stringBuilder);stringBuilder.append(")");}}
}

12. 題目12：非遞歸實現(xiàn)二叉樹前序遍歷

題目鏈接：144. 二叉樹的前序遍歷 - 力扣（LeetCode）

代碼：

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root == null){return ret;}TreeNode cur = root;   // 用于遍歷二叉樹Deque<TreeNode> stack = new ArrayDeque<>();while(cur != null || !stack.isEmpty()){while(cur != null){stack.push(cur);ret.add(cur.val);cur = cur.left;}TreeNode top = stack.pop();cur = top.right;}return ret;}
}

13. 題目13：非遞歸實現(xiàn)二叉樹中序遍歷

題目鏈接：94. 二叉樹的中序遍歷 - 力扣（LeetCode）

代碼：

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root == null){return ret;}TreeNode cur = root;Deque<TreeNode> stack = new ArrayDeque<>();while(cur != null || !stack.isEmpty()){while(cur != null){stack.push(cur);cur = cur.left;}TreeNode top = stack.pop();ret.add(top.val);cur = top.right;}return ret;}
}

14. 題目14：非遞歸實現(xiàn)二叉樹后序遍歷

題目鏈接：145. 二叉樹的后序遍歷 - 力扣（LeetCode）

代碼：

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root == null){return ret;}TreeNode cur = root;TreeNode prev = null;Deque<TreeNode> stack = new ArrayDeque<>();while(cur != null || !stack.isEmpty()){while(cur != null){stack.push(cur);cur = cur.left;}// 后序遍歷順序為：根->左->右TreeNode top = stack.peek();  // 不可以直接pop棧頂元素// 當(dāng)棧頂元素結(jié)點沒有右子樹時才可以打印根結(jié)點if(top.right == null || top.right == prev){ret.add(top.val);stack.pop();prev = top;}else{// 棧頂元素結(jié)點有右子樹，優(yōu)先遍歷右子樹后再打印根結(jié)點cur = top.right;}}return ret;}
}