目錄
1. 根據前序與中序構造二叉樹
2. 根據后序與中序構造二叉樹
1. 根據前序與中序構造二叉樹
根據前序與中序遍歷構造二叉樹
題目：給定一棵樹的前序遍歷 preorder 與中序遍歷
inorder，請構造二叉樹并回傳其根節點 ，例如：
?
可以點開上述鏈接查看題目，具體做法如下：
分析：從前序遍歷可以得到根結點，從中序中可以得到跟結點的左右子樹部分，我們在構造二叉樹的時候是從前序找根，再在中序中找根的左右子樹部分先創建根節點再分別創建跟的左子樹與跟的右子樹，這個程序是一個遞回，每次遞回都要確定在中序哪個區間找新的根，
注意：前序順序是根---左---右，所以還原的時候是根---左---右，這樣才使得index++成立，index為標記前序的根，index從前序的開始依次走向末尾
具體步驟：
1. 在前序遍歷中找根
2. 在中序遍歷找根，用pos標記分界點，pos的左右兩部分為遞回找左與遞回找右
3. 先還原根結點，再遞回還原根的左子樹，遞回還原根的右子樹
4. 遞回還原的時候是依據中序遍歷劃分的范圍
參考代碼：
class Solution {
int index = 0; //標記前序的根
public TreeNode buildTree(int[] preorder, int[] inorder) {
return reBuildTree(preorder,inorder,0,inorder.length);
}
public TreeNode reBuildTree(int[] preorder,int[] inorder,int left,int right){
//遞回回傳條件
if(index>=preorder.length || left>=right){
return null;
}
int pos = left;
//在中序中找根的位置
while(pos < right){
if(inorder[pos] == preorder[index]){
break;
}
pos++;
}
TreeNode root = new TreeNode(preorder[index]);//還原根
index++;
root.left = reBuildTree(preorder,inorder,left,pos);//遞回還原左
root.right = reBuildTree(preorder,inorder,pos+1,right);//遞回還原右
return root;
}
}2. 根據后序與中序構造二叉樹
根據后序與中序構造二叉樹
題目：根據一棵樹的中序遍歷與后序遍歷構造二叉樹，
例如：
?
可以點開上述鏈接查看題目，具體做法如下：
分析：后序遍歷可以確定根結點，中序遍歷可以得到根結點的左右子樹兩部分，所以還在中序遍歷中找根節點的位置，用pos標記，將中序遍歷分為兩個部分，再分別在這兩個部分中遞回構造根的左子樹與根的右子樹，
注意：后續遍歷是左---右---根，所以我們在還原的時候倒著還原，還原順序為：根---右---左，這樣使得index--成立，index為標記后續的根，它從后續的末尾依次走向開始
具體步驟：
1. 從后續遍歷中找到根
2. 在中序中找到根的位置，用pos標記將中序遍歷分為兩部分
3. 在pos標記的右部分遞回還原根的右子樹
4. 在pos標記的左部分遞回還原根的左子樹
參考代碼：
class Solution {
int index; //標記后序遍歷的根
public TreeNode buildTree(int[] inorder, int[] postorder) {
index = postorder.length-1; //后續的根
return reBuildTree(inorder,postorder,0,inorder.length);
}
public TreeNode reBuildTree(int[] inorder,int[] postorder,int left,int right){
//遞回回傳條件
if(index < 0 || left >= right){
return null;
}
//在中序遍歷中找到根的位置
int pos = left;
while(pos < right){
if(postorder[index] == inorder[pos]){
break;
}
pos++;
}
//還原根
TreeNode root = new TreeNode(postorder[index]);
index--;
root.right = reBuildTree(inorder,postorder,pos+1,right); //還原根的右
root.left = reBuildTree(inorder,postorder,left,pos); //還原根的左
return root;
}
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/377072.html
標籤：其他