Construct Binary Tree from Preorder and Inorder Traversal
update Aug 29, 2017 23:07
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
Basic Idea:
通过观察，我们可以发现 preorder 遍历的结果的第一个数一定是 root，而在 inorder list 中，root 会把左右两子树一分为二，利用这种性质，我们可以得到一种递归解法：
对于输入inorder lst 和 preorder lst，先标记 preorde[0] 作为 root，然后在 inorder 中查找 root 的位置；
这样就将两个 list 分为了两部分，分表为当前root左右子树的元素，对左右子树递归执行；
例如，对于input：
preorder: [1,2,4,5,7,3,6]
inorder: [4,2,7,5,1,3,6]我们可以看到，对于以 1 为 root 的树，我们可以用 1 将 inorder 分成两部分，递归传给下层函数的参数分别为：
left: right:
preorder: [2,3,5,7] preorder: [3,6]
inorder [4,2,7,5] inorder: [3,6]Java Code:
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(preorder, inorder);
}
private TreeNode helper(int[] preorder, int[] inorder) {
if (preorder.length == 0 ) return null;
if (preorder.length == 1) return new TreeNode(preorder[0]);
TreeNode root = new TreeNode(preorder[0]);
int root_idx = indexOf(inorder, preorder[0]);
int l_subtree_size = root_idx;
int r_subtree_size = inorder.length - root_idx - 1;
if (l_subtree_size > 0) {
root.left = helper(Arrays.copyOfRange(preorder, 1, l_subtree_size + 1), Arrays.copyOfRange(inorder, 0, root_idx));
}
if (r_subtree_size > 0) {
root.right = helper(Arrays.copyOfRange(preorder, l_subtree_size + 1, preorder.length),
Arrays.copyOfRange(inorder, root_idx + 1, inorder.length));
}
return root;
}
private int indexOf(int[] arr, int target) {
for (int i = 0; i < arr.length; ++i) {
if (arr[i] == target) return i;
}
return -1;
}
}Python Code:
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if not preorder:
return None
if len(preorder) == 1:
return TreeNode(preorder[0])
root = TreeNode(preorder[0])
root_idx = inorder.index(preorder[0])
left_size = root_idx
right_size = len(inorder) - root_idx - 1
if left_size:
root.left = self.buildTree(preorder[1 : left_size + 1], inorder[0 : root_idx])
if right_size:
root.right = self.buildTree(preorder[left_size + 1 :], inorder[root_idx + 1 :])
return rootupdate Dec 24, 2017 3:01
Update:
时间复杂度： 因为我们每次在inorder list中找root位置时候都要线性搜索，时间复杂度为 O(n^2)，可以预处理一下，用一个 map 存放所有 node 在 inorder list 中的 index，这样时间复杂度变为 O(n)，但空间复杂度从 O(1) 变为 O(n);
更新一个优化了时间复杂度的 Java 实现：
class Solution {
private Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.map = new HashMap<>();
for (int idx = 0; idx < inorder.length; ++idx) {
map.put(inorder[idx], idx);
}
return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
// return 为建成的tree的root，parameter是用来模拟传入了两个subarray`
private TreeNode helper(int[] preorder, int[] inorder, int pstart, int pend, int istart, int iend) {
if (pstart > pend) return null;
TreeNode root = new TreeNode(preorder[pstart]);
if (pstart == pend) return root;
int rootIndex = map.get(root.val);
int leftSize = rootIndex - istart;
// 这里主要是index各种计算，看不懂的话可以画图举例理解
root.left = helper(preorder, inorder, pstart + 1, pstart + leftSize, istart, rootIndex - 1);
root.right = helper(preorder, inorder, pstart + leftSize + 1, pend, rootIndex + 1, iend);
return root;
}
}update 2018-06-06 22:41:13
Update C++ Solution
运用之前的思路，用C++写了一个解法：
class Solution {
TreeNode* helper(unordered_map<int, int>& idxs, const vector<int>& preorder,
const vector<int>& inorder, int pre_start, int pre_end, int in_start, int in_end) {
if (pre_start > pre_end || in_start > in_end) return nullptr;
int root_val = preorder[pre_start];
int root_inorder_idx = idxs[root_val];
int leftSize = root_inorder_idx - in_start;
int rightSize = in_end - root_inorder_idx;
TreeNode* root = new TreeNode(root_val);
root->left = helper(idxs, preorder, inorder, pre_start + 1, pre_start + leftSize, in_start, root_inorder_idx - 1);
root->right = helper(idxs, preorder, inorder, pre_start + leftSize + 1, pre_end, root_inorder_idx + 1, in_end);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) return nullptr;
unordered_map<int, int> idxs;
for (int i = 0; i < inorder.size(); ++i) {
idxs.insert(make_pair(inorder[i], i));
}
int size = preorder.size();
return helper(idxs, preorder, inorder, 0, size - 1, 0, size - 1);
}
};update 2021-06-08
时隔三年的再一次更新，希望这次也会有好结果。
可以注意到，事实上没有必要维持每次递归时候preorder数组的右边界，因为我们每次都只需要取preorder中的第一个作为这次的root，所以只需要传入每次preorder的起点。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return construct(preorder, inorder, 0, 0, inorder.length - 1);
}
private TreeNode construct(int[] preorder, int[] inorder, int currPre, int left, int right) {
if (currPre == preorder.length || left > right) {
return null;
}
TreeNode root = new TreeNode(preorder[currPre]);
int indexInorder = left;
while (inorder[indexInorder] != preorder[currPre]) {
indexInorder++;
}
root.left = construct(preorder, inorder, currPre + 1, left, indexInorder - 1);
root.right = construct(preorder, inorder, currPre + indexInorder - left + 1, indexInorder + 1, right);
return root;
}
}Last updated