【Java數據結構】二叉樹詳解（四）

🔒文章目錄：

1.????前言~🥳🎉🎉🎉

2.給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先?

2.1第一種思路?

2.2第二種思路??

3.根據一棵樹的前序遍歷與中序遍歷構造二叉樹?

4.根據一棵樹的中序遍歷與后序遍歷構造二叉樹?

5.二叉樹創建字符串

6.二叉樹非遞歸實現前序遍歷

?7.二叉樹非遞歸實現中序遍歷

8.二叉樹非遞歸實現后序遍歷

9.總結

1.????前言~🥳🎉🎉🎉

Hello, Hello~ 親愛的朋友們👋👋，這里是E綿綿呀????。

如果你喜歡這篇文章，請別吝嗇你的點贊????和收藏📖📖。如果你對我的內容感興趣，記得關注我👀👀以便不錯過每一篇精彩。

當然，如果在閱讀中發現任何問題或疑問，我非常歡迎你在評論區留言指正🗨?🗨?。讓我們共同努力，一起進步！

加油，一起CHIN UP！💪💪

🔗個人主頁：E綿綿的博客
📚所屬專欄：

1.?JAVA知識點專欄

? ? ?? ?深入探索JAVA的核心概念與技術細節

2.JAVA題目練習

? ? ? ??實戰演練，鞏固JAVA編程技能

3.c語言知識點專欄

? ? ? ? 揭示c語言的底層邏輯與高級特性

4.c語言題目練習

? ? ? ? 挑戰自我，提升c語言編程能力

📘 持續更新中，敬請期待????

2.給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先?

?📌題目描述?

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）”?

2.1第一種思路?

📋題目思路?

首先，檢查根節點是否為null，如果是，則返回null。這是遞歸算法的基本情況之一，用于處理空樹的情況。

接下來，檢查根節點是否等于其中一個指定節點，如果是，則返回根節點。這是另一個基本情況，處理了當根節點就是目標節點之一的情況。

然后，分別遞歸地在左子樹和右子樹中尋找指定節點的最近公共祖先，并將結果存儲在left和right變量中。

如果左右子樹中都找到了指定節點，則說明當前根節點就是這兩個節點的最近公共祖先，返回當前根節點。

如果只有一個子樹找到了指定節點，那么這個子樹的返回值就是這兩個節點的最近公共祖先，返回該子樹的返回值。

如果左右子樹都沒有找到指定節點，則返回null。

這個算法是一個遞歸算法，通過深度優先搜索遍歷整個樹從而查找最近公共祖先。

?題目代碼??

 // 給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。public BTNode lowestCommonAncestor(BTNode root, BTNode p, BTNode q) {if(root==null)return null;if(root==p||root==q)return  root;BTNode left=lowestCommonAncestor(root.left,p,q);BTNode right=lowestCommonAncestor(root.right,p,q);if(left!=null&&right!=null)return  root;if(left==null&&right!=null)return  right;if(left!=null&&right==null)return  left;if(left==null&&right==null)return  null;return  null;}

2.2第二種思路??

📋題目思路??

首先定義了一個lowestCommonAncestor方法，接收三個參數：根節點root，和兩個指定節點p和q。

創建了兩個Stack對象，stack1和stack2，用于分別存儲從根節點到指定節點p和q的路徑。

調用getStack方法分別獲取從根節點到p和q的路徑，并將路徑存儲在stack1和stack2中。

如果兩條路徑都成功獲取，則進入后續處理。

獲取到路徑后，計算兩個棧的大小，并確保它們在最后一個共同節點處相等。如果不相等，則將較長的棧中的節點出棧，直到兩個棧的大小相等為止。

然后，同時從兩個棧中彈出元素，直到找到最后一個相同的節點。這個節點就是最近的公共祖先。

如果沒有找到共同節點，返回null。

在getStack方法中，也是一個遞歸方法，用于獲取從根節點到指定節點的路徑。它接收一個棧對象、根節點和目標節點作為參數。

如果根節點為null，返回false。

將當前節點加入棧中。

如果當前節點是目標節點，則返回true。

否則，遞歸地在左子樹和右子樹中查找目標節點。如果找到目標節點，則直接退出該方法且返回true。否則將棧頂元素彈出，并返回false。

我們這第二種思路利用棧和遞歸去解決問題的，比第一種思路要相對復雜點。

??題目代碼??

   public BTNode lowestCommonAncestor(BTNode root, BTNode p, BTNode q) {Stack<BTNode> stack1=new Stack<>();Stack<BTNode> stack2=new Stack<>();if (getStack(stack1,root,p)&&getStack(stack2,root,q)){int a= stack1.size();int b= stack2.size();while(a!=b){if(a>b) {stack1.pop();a--;}else{stack2.pop();b--;}}while(!stack1.isEmpty()){if(stack1.peek()==stack2.peek())return  stack1.peek();elsestack1.pop();stack2.pop();}return  null;}return  null;}public boolean getStack(Stack<BTNode> stack,BTNode root,BTNode p){if(root==null)return false;stack.push(root);if (root==p)return true;if(!(getStack(stack,root.left,p)||getStack(stack,root.right,p))) {stack.pop();return false;}return true;}

該題鏈接：給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先?

3.根據一棵樹的前序遍歷與中序遍歷構造二叉樹?

?📌題目描述?

給定兩個整數數組?preorder?和?inorder?，其中?preorder?是二叉樹的先序遍歷，?inorder?是同一棵樹的中序遍歷，請構造二叉樹并返回其根節點。

?📋題目思路?

我們需要實現一個構建二叉樹的方法 buildTree，根據給定的先序遍歷數組 preorder 和中序遍歷數組 inorder，返回構建的二叉樹的根節點。其中，通過靜態內部類 TreeNode 來表示二叉樹的每個節點，每個節點有一個值 value 和兩個指向左右子樹的 left、right 指針。

具體實現思路是：先序遍歷數組 preorder 的第一個元素為當前根節點，然后在中序遍歷數組 inorder 中找到該根節點的位置，從而確定左右子樹的范圍。而后通過遞歸方式依次構建左右子樹，并返回當前節點，最終返回整棵二叉樹的根節點。

其中，我們還要有getIndex 方法用于在中序遍歷數組中查找指定值的位置，還需要通過設置成員變量i去遍歷先序數組中的元素。

??題目代碼?

//給定兩個整數數組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，
// 請構造二叉樹并返回其根節點。
public class Test3 {public int i;static class TreeNode {int value;TreeNode left;TreeNode right;public TreeNode(int value) {this.value = value;}}public TreeNode buildTree(int[] preorder, int[] inorder) {return    build(preorder,inorder,0,inorder.length-1);}public int getIndex(int[] inorder,int value,int began,int end){for (int j = began; j <=end ; j++) {if(inorder[j]==value)return  j;}return  -1;}public  TreeNode  build(int[] preorder,int[] inorder,int began,int end) {if(began>end)return  null;TreeNode treeNode = new TreeNode(preorder[i]);int index = getIndex(inorder, preorder[i], began,end);i++;treeNode.left = build(preorder,inorder,began,index-1);treeNode.right=build(preorder,inorder,index+1,end);return  treeNode;}}

該題鏈接：根據一棵樹的前序遍歷與中序遍歷構造二叉樹?

4.根據一棵樹的中序遍歷與后序遍歷構造二叉樹?

?📌題目描述?

給定兩個整數數組?inorder?和?postorder?，其中?inorder?是二叉樹的中序遍歷，?postorder?是同一棵樹的后序遍歷，請你構造并返回這顆?二叉樹?。

?📋題目思路??

跟我們上一題思路差不多

我們需要實現一個構建二叉樹的方法 buildTree，根據給定的后序遍歷數組 postorder 和中序遍歷數組 inorder，返回構建的二叉樹的根節點。其中，通過靜態內部類 TreeNode 來表示二叉樹的每個節點，每個節點有一個值 value 和兩個指向左右子樹的 left、right 指針。

具體實現思路是：后序遍歷數組 postorder?的最后一個元素為當前根節點，然后在中序遍歷數組 inorder 中找到該根節點的位置，從而確定左右子樹的范圍。而后通過遞歸方式依次構建左右子樹，并返回當前節點，最終返回整棵二叉樹的根節點。

??題目代碼?

//給定兩個整數數組 inorder 和 postorder ，其中 inorder 是二叉樹的中序遍歷， postorder 是同一棵樹的后序遍歷，
// 請你構造并返回這顆 二叉樹 。
public class Test4 {public int i;static class TreeNode {int value;TreeNode left;TreeNode right;public TreeNode(int value) {this.value = value;}}public TreeNode buildTree(int[] inorder, int[] postorder) {i=postorder.length-1;return    build(postorder,inorder,0,inorder.length-1);}public int getIndex(int[] inorder,int value,int began,int end){for (int j = began; j <=end ; j++) {if(inorder[j]==value)return  j;}return  -1;}public TreeNode build(int[] preorder, int[] inorder, int began, int end) {if(began>end)return  null;TreeNode treeNode = new TreeNode(preorder[i]);int index = getIndex(inorder, preorder[i], began,end);i--;treeNode.right = build(preorder,inorder,index+1,end);treeNode.left=build(preorder,inorder,began,index-1);return  treeNode;}}

?該題鏈接：根據一棵樹的中序遍歷與后序遍歷構造二叉樹?

5.二叉樹創建字符串

📌題目描述?

給你二叉樹的根節點?root?，請你采用前序遍歷的方式，將二叉樹轉化為一個由括號和整數組成的字符串，返回構造出的字符串。

空節點使用一對空括號對?"()"?表示，轉化后需要省略所有不影響字符串與原始二叉樹之間的一對一映射關系的空括號對。

??📋題目思路??

定義了一個Solution1類，其中包含了一個靜態內部類TreeNode，用于表示二叉樹的節點。

tree2str方法是轉換函數的入口，接收一個根節點root，返回轉換后的字符串。

創建了一個StringBuilder對象stringBuilder，用于拼接轉換后的字符串。

如果根節點為null，直接返回空字符串。

將根節點的值添加到stringBuilder中。

調用getString方法來遞歸構建字符串。

getString方法是遞歸構建字符串的核心方法，接收一個StringBuilder對象和當前節點作為參數。

如果當前節點的左右子節點都為空，說明當前節點是葉子節點，直接返回。

根據當前節點的左右子節點情況，按照題目要求構建字符串：

如果左子節點為空而右子節點不為空，則添加"()"和右子節點的值。
如果右子節點為空而左子節點不為空，則添加左子節點的值。
如果左右子節點都不為空，則添加左子節點的值和右子節點的值。

繼續遞歸調用getString方法處理左右子節點。

最后返回構建好的字符串。

??題目代碼?

//給你二叉樹的根節點 root ，請你采用前序遍歷的方式，將二叉樹轉化為一個由括號和整數組成的字符串，返回構造出的字符串。
class Solution1 {static class TreeNode {int value;TreeNode left;TreeNode right;public  TreeNode(int value) {this.value = value;}}public String tree2str(TreeNode root) {StringBuilder stringBuilder=new StringBuilder();if(root==null)return  stringBuilder.toString();stringBuilder.append(root.value);getString (stringBuilder,root);return   stringBuilder.toString();}public void getString(StringBuilder stringBuilder,TreeNode root){if(root.left==null&&root.right==null)return  ;if(root.left==null&&root.right!=null) {stringBuilder.append("()");stringBuilder.append("(");stringBuilder.append(root.right.value);getString(stringBuilder,root.right);stringBuilder.append(")");}if(root.left!=null&&root.right==null){stringBuilder.append("(");stringBuilder.append(root.left.value);getString(stringBuilder,root.left);stringBuilder.append(")");}if(root.left!=null&&root.right!=null){stringBuilder.append("(");stringBuilder.append(root.left.value);getString(stringBuilder,root.left);stringBuilder.append(")");stringBuilder.append("(");stringBuilder.append(root.right.value);getString(stringBuilder,root.right);stringBuilder.append(")");}}}

該題鏈接：二叉樹創建字符串?

6.二叉樹非遞歸實現前序遍歷

📌題目描述?

用非遞歸的方式（循環方式）實現前序遍歷

?📋題目思路??

定義了一個preorderTraversal方法，接收一個根節點root，返回樹的前序遍歷結果。

創建了一個ArrayList對象list，用于存儲遍歷結果。

創建了一個Stack對象stack，用于輔助遍歷。

如果根節點為null，直接返回空的遍歷結果列表。

進入循環，直到根節點為null并且棧為空為止。

內部循環：在每次循環中，將當前節點的值加入到遍歷結果列表中，并將當前節點入棧。然后，沿著左子樹一直向下遍歷，直到遇到沒有左子節點的節點為止。

一旦當前節點的左子樹遍歷完成，將當前節點出棧，并將當前節點指向其右子節點。

重復步驟6和7，直到遍歷完成。

返回遍歷結果列表。

??題目代碼

   public List<Integer> preorderTraversal(BTNode root) {List<Integer> list=new ArrayList<>();Stack<BTNode> stack=new Stack<>();if(root==null)return list;while(root!=null||!stack.isEmpty()){while(root!=null){list.add(root.value);stack.push(root);root=root.left;}root= stack.pop().right;}return list;}

?該題鏈接：二叉樹非遞歸實現前序遍歷

?7.二叉樹非遞歸實現中序遍歷

📌題目描述?

用非遞歸的方式（循環方式）實現中序遍歷

??📋題目思路??

定義了一個inorderTraversal方法，接收一個根節點root，返回樹的中序遍歷結果。

創建了一個ArrayList對象list，用于存儲遍歷結果。

創建了一個Stack對象stack，用于輔助遍歷。

如果根節點為null，直接返回空的遍歷結果列表。

進入循環，直到根節點為null并且棧為空為止。

內部循環：在每次循環中，將當前節點的所有左子節點入棧，直到當前節點為空。

出棧一個節點，并將其右子節點作為當前節點。

將出棧節點的值添加到遍歷結果列表中。

重復步驟6到8，直到遍歷完成。

返回遍歷結果列表。

???題目代碼

public List<Integer> inorderTraversal(BTNode root) {List<Integer> list=new ArrayList<>();Stack<BTNode> stack=new Stack<>();if(root==null)return list;while(root!=null||!stack.isEmpty()){while (root!=null){stack.push(root);root=root.left;}BTNode btNode=stack.pop();root=btNode.right;list.add(btNode.value);}return list;}

該題鏈接：二叉樹非遞歸實現中序遍歷

8.二叉樹非遞歸實現后序遍歷

📌題目描述?

用非遞歸的方式（循環方式）實現后序遍歷

?📋題目思路??

定義了一個postorderTraversal方法，接收一個根節點root，返回樹的后序遍歷結果。

創建了一個ArrayList對象list，用于存儲遍歷結果。

創建了一個Stack對象stack，用于輔助遍歷。

如果根節點為null，直接返回空的遍歷結果列表。

進入循環，直到根節點為null并且棧為空為止。

內部循環：在每次循環中，將當前節點的所有左子節點入棧，直到當前節點為空。

在每次內部循環結束后，通過stack.peek()獲取當前棧頂節點，將其賦值給btNode。

定義prev節點，初始化為當前棧頂節點。

將root指向btNode的右子節點。

如果root為null，說明當前節點的左右子樹已經遍歷完畢，將當前節點的值加入到遍歷結果列表中，并將棧頂節點出棧。

檢查棧是否為空，如果為空，則遍歷結束，返回結果列表。

如果棧不為空，則將root重新指向棧頂節點的右子節點，然后從棧中取出節點，直到當前root節點與prev節點的右子節點不相等為止，將取出的節點加入到結果列表中。

重復步驟6到12，直到遍歷完成。

返回遍歷結果列表。

??題目代碼

   public List<Integer> postorderTraversal(BTNode root) {List<Integer> list=new ArrayList<>();Stack<BTNode> stack=new Stack<>();if(root==null)return list;while (root!=null||!stack.isEmpty()){while(root!=null){stack.push(root);root=root.left;}BTNode btNode= stack.peek();BTNode prev=btNode;root=btNode.right;if(root==null){list.add(stack.pop().value);if (stack.isEmpty())return list;root=stack.peek().right;while (root==prev){prev=stack.pop();list.add(prev.value);if(stack.isEmpty())return  list;root=stack.peek().right;}}}return  list;}}

該題鏈接：二叉樹非遞歸實現后序遍歷?