剑指offer-重建二叉树

2019-11-06 07:57:53

字体：大中小

来源：转载

供稿：网友

问题

题目：[重建二叉树]

思路

老问题了，递归建立。基本思路是，根据先序中的第一个节点。到中序序列去进行划分左右子树。然后递归建立左右子树即可。

代码

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: TreeNode* reConstructBinaryTree(vector<int> PRe,vector<int> vin) { return create( pre, 0, pre.size()-1, vin, 0, vin.size()-1 ); }private: TreeNode* create(const vector<int>& pre, int s1, int t1, const vector<int>& in, int s2, int t2) { if(s1 > t1) return NULL; TreeNode* root = new TreeNode(pre[s1]); int mid = 0; for(mid = s2; mid <= t2; ++mid){ if(in[mid] == pre[s1]) break; } int left_len = mid-s2; root->left = create( pre, s1+1, s1 + left_len, in, s2, mid-1 ); root->right = create(pre, s1+left_len+1, t1, in, mid+1, t2); return root; }};

上一篇：mybatis-generator IDEA 使用方法

下一篇：STM32调试问题及分析