-
Notifications
You must be signed in to change notification settings - Fork 0
/
07_reconstruct_tree.cpp
51 lines (45 loc) · 1.45 KB
/
07_reconstruct_tree.cpp
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};
BinaryTreeNode *TreeConstruct(int *preOrder,int *inOrder,int length)
{
if(nullptr == preOrder || nullptr == inOrder || length <= 0)
return nullptr;
return ConstructCore(preOrder,preOrder + length - 1,inOrder,inOrder + length - 1);
}
BinaryTreeNode *ConstructCore(int *pPreOrderStart,int *pPreOrderEnd,int *pInOrderStart,int *pInOrderEnd)
{
int rootValue = startPreOrder[0];
BinaryTreeNode *root = new BinaryTreeNode();
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = nullptr;
if(pPreOrderStart == pPreOrderEnd)
{
if(pInOrderStart == pInOrderEnd && (*pPreOrderStart) == (*pPreOrderEnd))
return root;
else
throw std::exception("invalid input");
}
//在中序遍历中找到根节点位置
int *rootInOrder = pInOrderStart;
while(rootInOrder <= pInOrderEnd && (*rootInOrder) != rootValue)
++rootInOrder;
if(rootInOrder == pInOrderEnd && *rootInOrder != rootValue)
throw std::exception("invalid input");
int leftLength = rootInOrder - pInOrderStart;
int *leftPreOrderEnd = pPreOrderStart + leftLength;
if(leftLength > 0)
{
//构建左子树
root->m_pLeft = ConstructCore(pPreOrderStart + 1,leftPreOrderEnd,pInOrderStart,rootInOrder - 1);
}
if(leftLength < pPreOrderEnd - pPreOrderStart)
{
//构建右子树
root->m_pRight = ConstructCore(leftPreOrderEnd + 1,pPreOrderEnd,rootInOrder + 1,pInOrderEnd);
}
return root;
}