用前序遍历和和中序遍历在本机检查结果
重建二叉树
http://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6
我写了前序遍历和中序遍历函数来检查,这是本机测试用的全部代码
#include<iostream> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { if (pre.empty() || vin.empty() || pre.size()!=vin.size()) return nullptr; TreeNode * root = new TreeNode(pre[0]); if (pre.size() == 1) return root; vector<int> left_pre; vector<int> left_vin; vector<int> right_pre; vector<int> right_vin; int i = 0; //left_vin while (vin[i]!=pre[0]) left_vin.push_back(vin[i++]); //right_vin while (i<vin.size()-1) right_vin.push_back(vin[++i]); int j; //left_pre for (j=0;j<pre.size();++j) { for (i=0;i<left_vin.size();++i) { if (pre[j] == left_vin[i]) { left_pre.push_back(pre[j]); break; } } if (left_pre.size() == left_vin.size()) break; } //right_pre for (j=0;j<pre.size();++j) { for (i=0;i<right_vin.size();++i) { if (pre[j] == right_vin[i]) { right_pre.push_back(pre[j]); break; } } if (right_pre.size() == right_vin.size()) break; } root->left = reConstructBinaryTree(left_pre, left_vin); root->right = reConstructBinaryTree(right_pre, right_vin); return root; } /*二叉树的前序遍历递归算法,使用二叉链表存储二叉树*/ void PreOrderTraverse(TreeNode* T) { if (T == NULL) return; printf("%d ", T->val);//访问根结点,可换为其他的对结点的操作 PreOrderTraverse(T->left);//先前序遍历左子树 PreOrderTraverse(T->right);//再前序遍历右子树 } /*二叉树中序遍历递归算法*/ void InOrderTraverse(TreeNode* T) { if (T== NULL) return; InOrderTraverse(T->left);//先中序遍历左子树(并不先访问根结点!) printf("%d ", T->val); InOrderTraverse(T->right);//最后中序遍历右子树 } int main() { //{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6} vector<int> pre = {1,2,4,7,3,5,6,8}; vector<int> vin = {4,7,2,1,5,3,8,6}; TreeNode* tree = reConstructBinaryTree(pre, vin); PreOrderTraverse(tree); cout << endl; InOrderTraverse(tree); return 0; }