本文共 1820 字，大约阅读时间需要 6 分钟。
p62 输入前序和中序遍历的结果（不包含重复的数字），重建二叉树。
主要是分析两个序列的规律，然后用递归的方式找到每一个根节点，从而完成构建。
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;class Node{public: Node(int a = 0, Node* b = nullptr, Node* c = nullptr) :value(a), left(b),right(c){} int value; Node* left,*right;};Node* createTree(vector & Pre, vector & Mid, int pStart, int pEnd, int mStart, int mEnd){ if (pStart < 0 || pEnd >= Pre.size() || mStart < 0 || mEnd >= Mid.size() || pStart > pEnd || mStart > mEnd) return nullptr; if (pEnd - pStart != mEnd - mStart) { cout << "Error : nums can't match " << endl; return nullptr; } int value = Pre[pStart]; Node* root = new Node(value); int pos = mStart; for (; pos <= mEnd; pos++) if (Mid[pos] == value) break; //判断是否存在错误 if (pos > mEnd) { cout << "Error : Cann't find the root " << endl; delete root; root = nullptr; return nullptr; } root->left = createTree(Pre, Mid, pStart + 1, pStart + pos - mStart, mStart, pos - 1); root->right = createTree(Pre, Mid, pStart + pos - mStart+1, pEnd, pos+1, mEnd); return root;}Node* solution(vector & a, vector & b){ return createTree(a, b, 0, a.size() - 1, 0, b.size() - 1);}void printTree(Node* root,int length=0){ if (root == nullptr) return; if (root->left != nullptr) printTree(root->left, length + 1); for (int i = 0; i < length; i++) cout << " "; cout << root->value << endl; if (root->right != nullptr) printTree(root->right, length + 1);}int main(int argc, char** args){ vector a = { 1, 2, 4, 7, 3, 5, 6 ,8}; vector b = { 4, 7, 2, 1, 5, 3, 8, 6 }; Node* root = solution(a, b); printTree(root); system("pause"); return 0;}
转载于:https://www.cnblogs.com/Oscar67/p/9579654.html