105. 從前序與中序遍歷序列構(gòu)造二叉樹給定兩個(gè)整數(shù)數(shù)組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構(gòu)造二叉樹并返回其根節(jié)點(diǎn)。

這題放選擇題里還能選出來，前序中序一起確定了一顆什么樣的樹。編程是一點(diǎn)都寫不來的，沒有思路。
看了答案
確定好一個(gè)節(jié)點(diǎn)的位置，在前序遍歷和中序遍歷中，這個(gè)節(jié)點(diǎn)左子樹和右子樹的節(jié)點(diǎn)個(gè)數(shù)是一樣多的
前序遍歷每次第一個(gè)節(jié)點(diǎn)就是當(dāng)前的根節(jié)點(diǎn)，將這個(gè)根節(jié)點(diǎn)放到中序遍歷中去找，找到的它的位置了。這個(gè)位置左邊的就是左子樹的所有節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)右邊的就是右子樹的所有節(jié)點(diǎn)。

確實(shí)不會(huì)，直接看答案把，只要是遞歸的時(shí)候?qū)τ谇靶蚝椭行蚰男┦亲笞訕淠男┦怯易訕湟_定好

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;}// 前序遍歷中的第一個(gè)節(jié)點(diǎn)就是根節(jié)點(diǎn)int preorder_root = preorder_left;// 在中序遍歷中定位根節(jié)點(diǎn)int inorder_root = indexMap.get(preorder[preorder_root]);// 先把根節(jié)點(diǎn)建立出來TreeNode root = new TreeNode(preorder[preorder_root]);// 得到左子樹中的節(jié)點(diǎn)數(shù)目int size_left_subtree = inorder_root - inorder_left;// 遞歸地構(gòu)造左子樹，并連接到根節(jié)點(diǎn)// 先序遍歷中「從 左邊界+1 開始的 size_left_subtree」個(gè)元素就對應(yīng)了中序遍歷中「從 左邊界 開始到 根節(jié)點(diǎn)定位-1」的元素root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);// 遞歸地構(gòu)造右子樹，并連接到根節(jié)點(diǎn)// 先序遍歷中「從 左邊界+1+左子樹節(jié)點(diǎn)數(shù)目 開始到 右邊界」的元素就對應(yīng)了中序遍歷中「從 根節(jié)點(diǎn)定位+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;// 構(gòu)造哈希映射，幫助我們快速定位根節(jié)點(diǎn)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）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。