點選上方“藍字”關注我們吧！
連結：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
根據一棵樹的前序周遊與中序周遊構造二叉樹。
注意:
你可以假設樹中沒有重複的元素。
例如，給出
前序周遊 preorder = [3,9,20,15,7]
中序周遊 inorder = [9,3,15,20,7]
傳回如下的二叉樹：
算法
Java
-
遞歸
官方題解：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/
1、前序周遊數組的第一個節點是跟節點，根據跟節點的值确定其在中序周遊數組的索引
2、中序周遊數組中，根節點左側的所有元素為根節點的左子樹，根節點右側的所有元素為根節點的右子樹
3、根據中序周遊數組的根節點索引，将中序周遊數組切割為左子樹數組，右子樹數組
4、根據中序周遊數組的左右子樹的數組，确定前序周遊數組中左右子樹的數組
5、确定了根節點的左右子樹的前序周遊數組和中序周遊數組，遞歸 1- 4步驟
class Solution { // 中序數組的哈希表，key：值；value：索引 Mapmap; public TreeNode buildTree(int[] preorder, int[] inorder) { map = new HashMap<>(); // 周遊中序數組，緩存哈希表 for (int i = 0; i < inorder.length; i++) { map.put(inorder[i], i); } return buildTreHelper(preorder, 0, preorder.length, inorder, 0, inorder.length); } /** * * @param preorder 前序周遊數組 * @param p_start 前序開始索引 * @param p_end 前序結束索引 * @param inorder 中序周遊數組 * @param i_start 中序開始索引 * @param i_end 中序結束索引 * @return 最終結果樹 */ private TreeNode buildTreHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) { // 遞歸終結條件 if (p_start == p_end || i_start == i_end) { return null; } // 确定root節點 TreeNode root = new TreeNode(preorder[p_start]); // 根節點在中序數組的索引 int rootIndex = map.get(root.val); // 左子樹節點個數 int leftCount = rootIndex - i_start; // 左子樹 root.left = buildTreHelper(preorder, p_start+1, p_start+1+leftCount, inorder, i_start, rootIndex); // 右子樹 root.right = buildTreHelper(preorder, p_start+leftCount+1, p_end, inorder, rootIndex+1, i_end); return root; }}
GitHub：https://github.com/huxq-coder/LeetCode
歡迎star
-END-
轉發，點贊，在看，安排一下？