https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> inMap = new HashMap<Integer, Integer>();
for(int i = 0; i < inorder.length; i++) {
inMap.put(inorder[i], i);
}
TreeNode root = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
return root;
}
public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
if(preStart > preEnd || inStart > inEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int inRoot = inMap.get(root.val);
int numsLeft = inRoot - inStart;//root的左子节点的数量
root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap);
//在前序遍历对应的vector中,如果root有左子节点的话那么对应的为vector中它对应的下一个节点
root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, inMap);
//在前序遍历对应的vector中,如果root有右节点的话,那么对应的右节点在vector中的索引为preStart + numsLeft + 1(numsLeft 是左节点的数量)
return root;
}
另外一种不使用递归的算法
class Solution {
public:
TreeNode* buildTree(vector<int> &pre, vector<int> &in) {
int i = 0, j = 0;
TreeNode *root = new TreeNode(0x80000000);
TreeNode *pp = NULL,*ptr = root;
stack<TreeNode*> sn;
sn.push(root);
while (j<in.size()) {
if(sn.top()->val == in[j]){//当该节点与 中序遍历的j节点相同说明 当前前序遍历数组中的i(即当前栈顶节点对应的下一个节点)所对应的节点为sn栈顶节点的右节点
//即相当于当前的栈顶节点已经”链接“上了左节点那么下一个索引i对应的节点应为该节点的右节点
pp = sn.top();
sn.pop();
j++;
}else if(pp){
ptr = new TreeNode(pre[i]);
pp->right = ptr;
pp = NULL;
sn.push(ptr);
i++;
}else{//一直左左左
ptr = new TreeNode(pre[i]);
sn.top()->left = ptr;
sn.push(ptr);
i++;
}
}
ptr = root->left;
delete root;
return ptr;
}
};