# Construct Binary Tree from Preorder and Inorder Traversal ### Source - leetcode: [Construct Binary Tree from Preorder and Inorder Traversal | LeetCode OJ](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) - lintcode: [(73) Construct Binary Tree from Preorder and Inorder Traversal](http://www.lintcode.com/en/problem/construct-binary-tree-from-preorder-and-inorder-traversal/) ~~~ Given preorder and inorder traversal of a tree, construct the binary tree. Example Given in-order [1,2,3] and pre-order [2,1,3], return a tree: 2 / \ 1 3 Note You may assume that duplicates do not exist in the tree. ~~~ ### 題解 二叉樹的重建，典型題。核心有兩點： 1. preorder 先序遍歷的第一個節點即為根節點。 1. 確定 inorder 數組中的根節點后其左子樹和右子樹也是 preorder 的左子樹和右子樹。 其中第二點是隱含條件，數組中沒有重復元素，故可以根據先序遍歷中第一個元素（根節點）得到根節點的值，然后在 inorder 中序遍歷的數組中搜索得到根節點的索引值，即為左子樹，右邊為右子樹。根據中序遍歷中左子樹的索引確定先序遍歷數組中左子樹的起止索引。遞歸直至處理完所有數組元素。 ### Java ~~~ /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** *@param preorder : A list of integers that preorder traversal of a tree *@param inorder : A list of integers that inorder traversal of a tree *@return : Root of a tree */ public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null || inorder == null) return null; if (preorder.length == 0 || inorder.length == 0) return null; if (preorder.length != inorder.length) return null; TreeNode root = helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); return root; } private TreeNode helper(int[] preorder, int prestart, int preend, int[] inorder, int instart, int inend) { // corner cases if (prestart > preend || instart > inend) return null; // build root TreeNode int root_val = preorder[prestart]; TreeNode root = new TreeNode(root_val); // find index of root_val in inorder[] int index = findIndex(inorder, instart, inend, root_val); // build left subtree root.left = helper(preorder, prestart + 1, prestart + index - instart, inorder, instart, index - 1); // build right subtree root.right = helper(preorder, prestart + index - instart + 1, preend, inorder, index + 1, inend); return root; } private int findIndex(int[] nums, int start, int end, int target) { for (int i = start; i <= end; i++) { if (nums[i] == target) return i; } return -1; } } ~~~ ### 源碼分析 由于需要知道左右子樹在數組中的索引，故需要引入輔助方法。找根節點這個大家都能很容易地想到，但是最關鍵的一步——找出左右子樹的起止索引，這一點就不那么直接了，老實說想了很久忽略了這個突破點。 ### 復雜度分析 `findIndex` 時間復雜度近似 O(n)O(n)O(n), `helper` 遞歸調用，每次調用都需要找中序遍歷數組中的根節點，故總的時間復雜度為 O(n2)O(n^2)O(n2). 原地生成最終二叉樹，空間復雜度為 O(1)O(1)O(1). ### Reference - [Construct Binary Tree from Preorder and Inorder Traversal 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/construct-binary-tree-from-preorder-and-inorder-traversal/)