LeetCode 105 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.
Diffculty
Medium
Similar Problems
[LeetCode 106] Construct Binary Tree from Inorder and Postorder Traversal M
Analysis
preorder 的遍历顺序是：根 - 左 - 右。从其形成的序列来说，根节点在最前面，后面部分存在一个分割点，前半部分是根的左子树，后半部分是根的右子树。 inorder 的遍历顺序是：左 - 根 - 右，从其形成的序列来说，根节点的左边部分是其左子树，右边部分是其右子树。
当我们从上向下构建树时，我们可以通过 Pre Order 序列先找到第一个根节点的值，但是如何知道其后面的左右子数所形成的两个序列是在哪里分割的呢？ 这就要依靠 In Order 序列来帮忙，我们根据已经在 Pre Order 中定位好的根节点的值，到中序序列中去寻找这个根节点，根据这个根的坐标，我们可以知道这个根左子树有多少个节点，右子树有多少个节点。然后我们根据这个信息将先序遍历序列分割，通过递归再次取每个部分的第一个作为根，同时为了下一次能准确的计算出左右子树各有多少节点，我们也要同时对中序遍历序列进行分割。
Solutions
class Solution {
public:
int preStart;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
preStart = 0;
if(preorder.size() == 0 || inorder.size() == 0) return nullptr;
return helper(0, inorder.size() - 1, preorder, inorder);
}
TreeNode* helper(int inStart, int inEnd, vector<int>& preorder, vector<int>& inorder){
if(preStart > preorder.size() || inStart > inEnd){ // Base情况
return nullptr;
}
TreeNode *root = new TreeNode(preorder[preStart]);
int inMid = 0;
for(int i = inStart ; i <= inEnd; i++){ // 找到根在中序序列中的位置，从而知道先序中的分割点
if(inorder[i] == root->val){
inMid = i;
break;
}
}
preStart++;
root->left = helper(inStart, inMid - 1, preorder, inorder); // 例如先序序列 1(234)(567) 中 2 是左子树的根
root->right = helper(inMid + 1, inEnd, preorder, inorder); // 先序序列 1(234)(567) 中 5 是右子树的根
return root;
}
};