105. 從前序與中序遍歷序列構造二叉樹給定兩個整數數組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構造二叉樹并返回其根節點。
這題放選擇題里還能選出來，前序中序一起確定了一顆什么樣的樹。編程是一點都寫不來的，沒有思路。
看了答案
確定好一個節點的位置，在前序遍歷和中序遍歷中，這個節點左子樹和右子樹的節點個數是一樣多的
前序遍歷每次第一個節點就是當前的根節點，將這個根節點放到中序遍歷中去找，找到的它的位置了。這個位置左邊的就是左子樹的所有節點，這個節點右邊的就是右子樹的所有節點。
確實不會，直接看答案把，只要是遞歸的時候對于前序和中序哪些是左子樹哪些是右子樹要確定好
class Solution {private Map<Integer, Integer> indexMap;public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left > preorder_right) {return null;}// 前序遍歷中的第一個節點就是根節點int preorder_root = preorder_left;// 在中序遍歷中定位根節點int inorder_root = indexMap.get(preorder[preorder_root]);// 先把根節點建立出來TreeNode root = new TreeNode(preorder[preorder_root]);// 得到左子樹中的節點數目int size_left_subtree = inorder_root - inorder_left;// 遞歸地構造左子樹，并連接到根節點// 先序遍歷中「從 左邊界+1 開始的 size_left_subtree」個元素就對應了中序遍歷中「從 左邊界 開始到 根節點定位-1」的元素root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);// 遞歸地構造右子樹，并連接到根節點// 先序遍歷中「從 左邊界+1+左子樹節點數目 開始到 右邊界」的元素就對應了中序遍歷中「從 根節點定位+1 到 右邊界」的元素root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 構造哈希映射，幫助我們快速定位根節點indexMap = new HashMap<Integer, Integer>();for (int i = 0; i < n; i++) {indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);}
}作者：力扣官方題解
鏈接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/255811/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
)
)
