目錄
- 1. 題目
- 2. 解題思路
- 個人思路
- 3. 資料型別功能函式總結
- 4. java代碼
1. 題目
輸入某二叉樹的前序遍歷和中序遍歷的結果，請構建該二叉樹并回傳其根節點，
假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
限制：
0 <= 節點個數 <= 5000
作者：Krahets
鏈接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/99lxci/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
2. 解題思路
個人思路
每次查找前序遍歷的節點0作為root節點，在中序遍歷中查找root節點所在位置，根據位置下標i將中序遍歷陣列分為左右兩個左右子陣列[0,i-1]和[i+1,len-1]，對前序遍歷陣列，根據左右子樹組的長度相同同樣進行分組劃分，然后遞回呼叫函式，處理左右子樹，
3. 資料型別功能函式總結
//陣列
int[] array_name=new int[len];//陣列定義
int len=array_name.length;//獲得陣列長度
4. java代碼
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0&&inorder.length==0){//特殊情況，也是遞回的邊界條件
return null;
}
else{
//構造根節點
int root_val=preorder[0];//前序遍歷的首元素為根節點的值
TreeNode root=new TreeNode(root_val);//創建根節點
//在中序遍歷陣列中查找根節點位置
int find_root=0;
int i=0;
for(i=0;i<inorder.length&&find_root==0;i++){
if(inorder[i]==root_val){
find_root=1;
}
}//此時得到下標i+1，[0,i-1][i][i+1,len-1]
//陣列二分
i--;
int[] left_inorder=new int[i];
int[] right_inorder=new int[inorder.length-i-1];
int[] left_preorder=new int[i];
int[] right_preorder=new int[inorder.length-i-1];
for(int j=0;j<i;j++){
left_inorder[j]=inorder[j];
left_preorder[j]=preorder[j+1];
}
for(int j=i+1;j<inorder.length;j++){
right_inorder[j-i-1]=inorder[j];
right_preorder[j-i-1]=preorder[j];
}
//遞回呼叫
root.left= buildTree(left_preorder, left_inorder);
root.right= buildTree(right_preorder, right_inorder);
return root;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/547605.html
標籤：Java