我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 105. 從前序與中序遍歷序列構造二叉樹
題目
根據一棵樹的前序遍歷與中序遍歷構造二叉樹，
注意:
你可以假設樹中沒有重復的元素，
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
回傳如下的二叉樹：
3
/ \
9 20
/ \
15 7
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
前序遍歷：根左右
中序遍歷：左根右
首先很容易得到前序遍歷的首個元素就是樹的根，若跟元素為root，那么：
- 在中序遍歷陣列root元素的左側部分就是樹的左子樹[0,R-1]；
- 在中序遍歷陣列root元素的右側部分就是樹的右子樹[R+1,length]；
且： - 前序遍歷的[1,R+1]是根的左子樹；
- 前序遍歷的[R+2,length]是根的右子樹；
根據以上分析是可以遞回重建二叉樹的；
思路1-分割陣列對應到子樹重建
根據上面的分析，分割陣列，每次新建當前節點為上層的子節點，直至處理完陣列；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $ 分割陣列需要的空間
思路2-不分割陣列，控制雙指標移動構建
因為遞回分割需要創建新陣列，所以思路1是非常耗時的，如果直接對原陣列元素處理不用新建陣列將有很大的提速；
先序遍歷的[0]在中序遍歷里的位置若為i，那么i-1在順序上是兩個遍歷處理的左子樹的最后一個節點，i+1以及之后的節點就是右子樹了；
那么可以以這個條件作為構建左子樹完畢的退出條件，退出后繼續構建右子樹；
所以，記錄雙指標分別對應兩個遍歷，i-先序遍歷，j-中序遍歷：
- [i]！=[j]，遞回構建左子樹，i++；
- [i]==[j]，i++，j++，跳過根節點，開始遞回構建右子樹；
- j==length構建完畢；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $ 遞回堆疊的深度，最差時
演算法原始碼示例
package leetcode;
import java.util.Arrays;
/**
* @author ZhouJie
* @date 2020年5月22日 下午1:28:22
* @Description: 105. 從前序與中序遍歷序列構造二叉樹
*
*/
public class LeetCode_0105 {
}
// Definition for a binary tree node.
class TreeNode_0105 {
int val;
TreeNode_0105 left;
TreeNode_0105 right;
TreeNode_0105(int x) {
val = x;
}
}
class Solution_0105 {
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午1:29:25
* @param: @param preorder
* @param: @param inorder
* @param: @return
* @return: TreeNode_0105
* @Description: 1-分割陣列對應到子樹遞回處理；
*
*/
public TreeNode_0105 buildTree_1(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return null;
} else {
TreeNode_0105 root = new TreeNode_0105(preorder[0]);
for (int i = 0; i < inorder.length; i++) {
if (preorder[0] == inorder[i]) {
root.left = buildTree_1(Arrays.copyOfRange(preorder, 1, i + 1), Arrays.copyOfRange(inorder, 0, i));
root.right = buildTree_1(Arrays.copyOfRange(preorder, i + 1, preorder.length),
Arrays.copyOfRange(inorder, i + 1, inorder.length));
break;
}
}
return root;
}
}
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午2:02:20
* @param: @param preorder
* @param: @param inorder
* @param: @return
* @return: TreeNode_0105
* @Description: 2-直接在陣列上遞回，不分割陣列，效率高；
*
*/
private int indexPreorder = 0;
private int indexInorder = 0;
public TreeNode_0105 buildTree_2(int[] preorder, int[] inorder) {
return buildHelper(preorder, inorder, null);
}
private TreeNode_0105 buildHelper(int[] preorder, int[] inorder, TreeNode_0105 node) {
if (node != null && node.val == inorder[indexInorder] || indexInorder == preorder.length) {
return null;
}
// 開始構建左子樹
TreeNode_0105 root = new TreeNode_0105(preorder[indexPreorder]);
// 先從preorder開始處理，當處理到等于inorder[0]的節點時，表明根的左子樹已經構建完成，可以開始遞回構建根的右子樹了
if (preorder[indexPreorder] == inorder[indexInorder]) {
indexPreorder++;
indexInorder++;
} else {
indexPreorder++;
root.left = buildHelper(preorder, inorder, root);
indexInorder++;
}
// 對于根而言，開始右子樹的遞回構建
root.right = buildHelper(preorder, inorder, node);
return root;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/185729.html
標籤：Java