今天的題目為105.Construct Binary Tree from Preorder and Inorder Traversal,題目再叫我們以前序和 中序的結果,重建原本的二元樹結構。
以下為程式碼以及解說:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private Map<Integer, Integer> inorderIndexMap; // 儲存中序遍歷中每個值的位置
private int preorderIndex = 0; // 用來追蹤目前處理到的前序節點
public TreeNode buildTree(int[] preorder, int[] inorder) {
inorderIndexMap = new HashMap<>();
// 將中序遍歷的值與索引存入 map,方便快速查找
for (int i = 0; i < inorder.length; i++) {
inorderIndexMap.put(inorder[i], i);
}
// 從整個範圍開始建樹
return buildSubTree(preorder, 0, inorder.length - 1);
}
private TreeNode buildSubTree(int[] preorder, int left, int right) {
// 如果左邊界超過右邊界,表示這部分沒有節點
if (left > right) return null;
// 取得目前的根節點值(來自前序遍歷)
int rootVal = preorder[preorderIndex++];
TreeNode root = new TreeNode(rootVal);
// 在中序遍歷中找到根節點的位置
int inorderIndex = inorderIndexMap.get(rootVal);
// 遞迴建構左子樹與右子樹
root.left = buildSubTree(preorder, left, inorderIndex - 1);
root.right = buildSubTree(preorder, inorderIndex + 1, right);
return root;
}
}
我覺得今天的也有點難,前、中序要搞清楚才行