小白一次AC LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal的要点
题目意思是，给你一颗树的前序遍历和中序遍历，让你重建这棵树。
这道题本科数据结构是讲过的，期末考试，考研这种题目也经常有，LeetCode刷题班又听许老师讲了一遍，老师思路讲的很好了，我就说说本题目如何练自己一次Bug-Free的能力，一次AC的要点在于
- 中序遍历找到根节点后，算出到中序遍历左子树的数量n，那么前序遍历根节点后n个就是左子树的节点，根节点以后的就是右子树的节点，不明白的画几个例子。
- 快速写出处理树常见问题的框架代码。
- 根据要点1，计算出左右子树的开始和结束下标，注意整数前开后闭区间[st, end)一共有end - st个数，[st, end]有end-st 1个数，不懂的童鞋算一下就好。
- 然后只要把左右子树的下标填补进去，我下面给出了两种写法本质是一样的，都是一次AC。
Construct Binary Tree from Preorder and Inorder Traversal Accepted 20 ms cpp
Construct Binary Tree from Preorder and Inorder Traversal Accepted 30 ms cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode *ansRoot = NULL;
if (preorder.size() && inorder.size() == 0){
return ansRoot;
}
ansRoot = ConstructTree(ansRoot, preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
return ansRoot;
}
TreeNode *ConstructTree(TreeNode * root, vector<int> &pre, int st1, int end1, vector<int> &in, int st2, int end2){
if (st1 >= pre.size() || st2 > end2){
return NULL;
}
root = new TreeNode(pre[st1]);
int pos = -1;
for (int i = st2; i <= end2; ++i){
if(in[i] == pre[st1]){
pos = i;
}
}
if (pos == -1){
return NULL;
}
int nLeft = pos - st2;//因为pos是跟节点，所以[)区间可以直接减
root->left = ConstructTree(root, pre, st1 + 1, st1 + nLeft - 1, in, st2, pos - 1);
root->right = ConstructTree(root, pre, st1 + nLeft + 1, end1, in, pos + 1, end2 );
//root->left = ConstructTree(root, pre, st1 + 1, st1 + nLeft - 1, in, st2, st2 + nLeft - 1);
//root->right = ConstructTree(root, pre, st1 + nLeft + 1, end1, in, st2 + nLeft + 1, end2 );
return root;
}
};
