根據前序和中序重構二叉樹
#include <iostream>
#include <vector>
using namespace std;
typedef struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> in)
{
if (pre.size() == 0)
return NULL;
TreeNode* root = new TreeNode(pre[0]);
int i;
for (i = 0; i < in.size() && in[i] != pre[0]; i++);
vector<int> pre_left, in_left, pre_right, in_right;
int pre_i = 1;
for (int j = 0; j < in.size(); j++)
{
if (j < i)
{
in_left.push_back(in[j]);//中序遍歷 左子樹中序遍歷陣列
pre_left.push_back(pre[pre_i]);//前序遍歷 左子樹前序遍歷陣列
pre_i++;
}
else if (j > i)
{
in_right.push_back(in[j]);
pre_right.push_back(pre[pre_i]);
pre_i++;
}
}
root->left = reConstructBinaryTree(pre_left, in_left);
root->right = reConstructBinaryTree(pre_right, in_right);
return root;
}
int main()
{
vector<int> pre;
pre.resize(1000);
pre.push_back(1);
pre.push_back(2);
pre.push_back(4);
pre.push_back(7);
pre.push_back(3);
pre.push_back(5);
pre.push_back(6);
pre.push_back(8);
vector<int> in;
in.resize(1000);
in.push_back(4);
in.push_back(7);
in.push_back(2);
in.push_back(1);
in.push_back(5);
in.push_back(6);
in.push_back(8);
in.push_back(6);
TreeNode* root=reConstructBinaryTree(pre, in);
system("pause");
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/8134.html
標籤：C++ 語言
上一篇：VS2015為什么release模式下計算結果比debug更精確？如何做到一致
下一篇：銀行對企業貸款的量化評估分析