# Leetcode: Construct Binary Tree from Preorder and Inorder Traversal

Note: You may assume that duplicates do not exist in the tree. 根据前序遍历和中序遍历结果构造二叉树。

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
private:
TreeNode *makeNode(vector<int>::iterator preBegin, vector<int>::iterator preEnd, vector<int>::iterator inBegin, vector<int>::iterator inEnd)
{
if (preBegin == preEnd) return nullptr;
//从中序遍历结果中找出根节点（根节点在前序遍历中是第一个节点）
vector<int>::iterator itRoot = find(inBegin, inEnd, *preBegin);
TreeNode *root = new TreeNode(*itRoot);
//计算根的左子树节点个数
int leftSize = itRoot - inBegin;
//在中序遍历结果中根节点的左边是左子树中序遍历结果，右边是右子树中序遍历结果
//在前序遍历结果中除去根节点前leftSize个节点是左子树前序遍历结果，后面的节点是右子树前序遍历结果
root->left = makeNode(preBegin + 1, preBegin + leftSize + 1, inBegin, itRoot);
root->right = makeNode(preBegin + leftSize + 1, preEnd, itRoot + 1, inEnd);
return root;
}
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
{
if (preorder.empty()) return nullptr;
TreeNode *root = makeNode(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
return root;
}
};```

```template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);

Find value in range
Returns an iterator to the first element in the range [first,last) that compares equal to val. If no such element is found, the function returns last.

The function uses operator== to compare the individual elements to val.```

```class Solution
{
private:
template <typename T>
TreeNode *makeNode(T preBegin, T preEnd, T inBegin, T inEnd)
{
if (preBegin == preEnd) return nullptr;
auto itRoot = find(inBegin, inEnd, *preBegin);
TreeNode *root = new TreeNode(*itRoot);
int leftSize = itRoot - inBegin;
root->left = makeNode(preBegin + 1, preBegin + leftSize + 1, inBegin, itRoot);
root->right = makeNode(preBegin + leftSize + 1, preEnd, itRoot + 1, inEnd);
return root;
}
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
{
if (preorder.empty()) return nullptr;
TreeNode *root = makeNode(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
return root;
}
};```

Java参考代码： 思路和上面一样，不过Java从数组中选择某个元素需要进行遍历（也可以转成List或者Set，但是遍历效率最高）上面C++代码中使用的是find函数。 有时候感觉C++代码还是挺简洁的！

```/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private TreeNode makeNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
if (preBegin == preEnd) return null;
int index = 0;
for (int i = inBegin; i < inEnd; i++) {
if (inorder[i] == preorder[preBegin]) {
index = i;
}
}
int leftSize = index - inBegin;
TreeNode root = new TreeNode(preorder[preBegin]);
root.left = makeNode(preorder, preBegin + 1, preBegin + leftSize + 1 , inorder, inBegin, inBegin + leftSize);
root.right = makeNode(preorder, preBegin + leftSize + 1, preEnd, inorder, index + 1, inEnd);
return root;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) return null;
TreeNode root = makeNode(preorder, 0, preorder.length ,inorder, 0, inorder.length);;
return root;
}
}```

0 条评论

## 相关文章

29640

### tendermint-peers讲解

Peer Exchange Reactor （PEX）确保与好的peers进行连接和通信

12840

15320

54330

### 十年Java架构师大厂实战（年薪80W）

BAT一直是程序员心神向往的地方，那些最最前沿的一线互联网技术都出自这些合称为大厂的地方，那里人才济济，哪怕实战经验不好的程序员进了那里，都会受到技术的熏陶，培...

21120

12830

10720

17720

13620

31140