## DEV Community

IQIUM

Posted on • Updated on

# 【剑指 Offer.07 重建二叉树】

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

## 递归方法

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

（设定先序遍历为preorder，中序遍历为inorder）

• 设定preorder[0] 为根节点 root
• 在 inorder 中寻找根节点所在的位置，然后计算 左子树 的结点个数
• 然后就可以递归建树了

``````class Solution {
public:
unordered_map<int, int> index;
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
int n = preorder.size();
for (int i = 0; i < n; i++) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}

TreeNode *myBuildTree(vector<int> &preorder, vector<int> &inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return nullptr;
}
int root_pre_idx = preorder_left;
TreeNode *root = new TreeNode(preorder[root_pre_idx]);
int root_in_idx = index[preorder[root_pre_idx]];
int left_tree_cnt = root_in_idx - inorder_left;
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + left_tree_cnt, inorder_left, root_in_idx - 1);
root->right = myBuildTree(preorder, inorder, preorder_left + left_tree_cnt + 1, preorder_right, root_in_idx + 1, inorder_right);
return root;
}
};
``````

DEV Community

Timeless DEV post...

## Git Concepts I Wish I Knew Years Ago

The most used technology by developers is not Javascript.

It's not Python or HTML.

It hardly even gets mentioned in interviews or listed as a pre-requisite for jobs.

I'm talking about Git and version control of course.