Tuesday, November 11, 2014

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

Binary tree一共3种访问顺序：preorder, inorder, postorder。这道题目的推广就是给定一个binary tree的两种访问顺序，重构该binary tree。这类题目给定的两个排序中，如果包括了inorder，且没有重复元素，就非常好解了。解这类题有两个关键点：

1. 在inorder中寻找root的位置，从而从序列中分割出左右子树。

Inorder:     left subtree | root | right subtree
Preorder:   root | left subtree | right subtree
Postorder: left subtree | right subtree | root

2. 递归构建

root->left = construct(inorder(left subtree), preorder(left subtree))
root->right = construct(inorder(right subtree), preorder(right subtree))

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27``` ```class Solution { public: TreeNode *buildTree(vector &preorder, vector &inorder) { if(preorder.size()!=inorder.size()) return NULL; int n = preorder.size(); return buildBT(preorder, inorder, 0, n-1, 0, n-1); } TreeNode *buildBT(vector &preorder, vector &inorder, int s1, int e1, int s2, int e2) { if(s1>e1 || s2>e2) return NULL; TreeNode *root = new TreeNode(preorder[s1]); int rootIndex = -1; // root index in inorder for(int i=s2; i<=e2; i++) { if(inorder[i]==root->val) { rootIndex = i; } } if(rootIndex==-1) return NULL; int leftTreeSize = rootIndex - s2; int rightTreeSize = e2 - rootIndex; root->left = buildBT(preorder, inorder, s1+1, s1+leftTreeSize, s2, rootIndex-1); root->right = buildBT(preorder, inorder, e1-rightTreeSize+1, e1, rootIndex+1, e2); return root; } }; ```