-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution105.cpp
More file actions
37 lines (34 loc) · 1.17 KB
/
Solution105.cpp
File metadata and controls
37 lines (34 loc) · 1.17 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//
// Solution105.cpp
// Algorithm
//
// Created by Pancf on 2020/12/6.
// Copyright © 2020 Pancf. All rights reserved.
//
#include "Solution105.hpp"
static TreeNode* build(std::vector<int> &preorder, std::vector<int> &inorder, int leftIdx, int rightIdx, int rootIdxInPreorder)
{
if (leftIdx == rightIdx) {
// leaf node
TreeNode *node = new TreeNode(inorder[leftIdx]);
return node;
}
int rootIdx = leftIdx;
for (int i = leftIdx; i <= rightIdx; ++i) {
if (preorder[rootIdxInPreorder] == inorder[i]) {
rootIdx = i;
break;
}
}
TreeNode *root = new TreeNode(inorder[rootIdx]);
if (rootIdx > leftIdx) root->left = build(preorder, inorder, leftIdx, rootIdx - 1, rootIdxInPreorder + 1);
if (rootIdx < rightIdx) root->right = build(preorder, inorder, rootIdx + 1, rightIdx, rootIdxInPreorder + rootIdx - leftIdx + 1);
return root;
}
TreeNode* Solution105::buildTree(std::vector<int> &preorder, std::vector<int> &inorder)
{
if (preorder.empty() || inorder.empty()) return nullptr;
int size = (int)preorder.size();
auto root = build(preorder, inorder, 0, size - 1, 0);
return root;
}