題目描述
根據(jù)前序遍歷和中序遍歷樹構(gòu)造二叉樹.
樣例
給出中序遍歷：[1,2,3]和前序遍歷：[2,1,3]. 返回如下的樹:
2
/ \
1 3
思路
先序遍歷的第一個(gè)數(shù)為根值承耿，在中序遍歷的數(shù)組中找到該值，并則在該值左邊為其左子樹，右邊為其右子樹。
實(shí)現(xiàn)
/**
* @param preorder : 樹的先序遍歷列表
* @param inorder : 樹的中序遍歷列表
* @return : Root of a tree
*/
/**
使用先序遍歷和中序遍歷構(gòu)造樹的遞歸方法
@param preorder 樹的先序遍歷列表
@param inorder 樹的中序遍歷列表
@param preStart 樹的先序遍歷列表起始位置
@param preEnd 樹的先序遍歷列表結(jié)束位置
@param inStart 樹的中序遍歷列表起始位置
@param inEnd 樹的中序遍歷列表結(jié)束位置
@return 根節(jié)點(diǎn)
*/
TreeNode * buildTreeCore(vector<int> &preorder, vector<int> &inorder,int preStart, int preEnd, int inStart, int inEnd){
//構(gòu)造根節(jié)點(diǎn)
int rootVal = preorder[preStart];
TreeNode *root = new TreeNode(rootVal);
if (preStart == preEnd) {
return root;
}
//找到在中序遍歷中的根節(jié)點(diǎn)
int indexOfRoot = inStart;
while (rootVal != inorder[indexOfRoot] && indexOfRoot < inEnd) {
indexOfRoot++;
}
//判斷是否存在左子樹，若有則遞歸構(gòu)造左子樹
if (indexOfRoot > inStart) {
root -> left = buildTreeCore(preorder, inorder, preStart + 1, preStart + (indexOfRoot - inStart), inStart, indexOfRoot - 1);
}
//判斷是否存在右子樹箍鼓，若有則遞歸構(gòu)造右子樹
if (indexOfRoot < inEnd) {
root -> right = buildTreeCore(preorder, inorder, preStart + (indexOfRoot - inStart) + 1, preEnd, indexOfRoot+1, inEnd);
}
return root;
}
/**
使用先序遍歷和中序遍歷構(gòu)造樹
@param preorder 樹的先序遍歷列表
@param inorder 樹的中序遍歷列表
@return 根節(jié)點(diǎn)
*/
TreeNode* buildTree(vector<int> &preorder, vector<int> &inorder) {
//參數(shù)檢查
if (preorder.size() <= 0 ||
inorder.size() <= 0 ||
preorder.size() != inorder.size()) {
return NULL;
}
TreeNode *root = buildTreeCore(preorder, inorder, 0, (int)preorder.size()-1, 0, (int)inorder.size() - 1);
return root;
}
