以前序遍历为例，仔细理解根左右： 1.1为根，打印1 2.进入1的左子树247,2为根，打印2 3.进入2的左子树47,4为根，打印4 4.进入4的左子树，但是4无左子树 5.进入4的右子树7，7为根，打印7 6.进入7的左子树，但是7无左子树 7.进入7的右子树，但是7无右子树 8.进入2的右子树，但是2无右子树 9.进入1的右子树3568，3为根，打印3 10.进入3的左子树5,5为根，打印5 11.进入5的左子树，但是5无左子树 12.进入5的右子树，但是5无右子树 13.进入3的右子树68，6为根，打印6 14.进入6的左子树8,8为根，打印8
以中序遍历为例，仔细理解左根右： 1.进入1的左子树247 2.进入2的左子树47 3.进入4的左子树 4.4无左子树 5.打印4 6.进入4的右子树7 7.进入7的左子树 8.7无左子树 9.打印7 10.进入7的右子树 11.7无右子树 12.打印2 13.进入2的右子树 14.2无右子树 15.打印1 16.进入1的右子树3568 17.进入3的左子树5 18.进入5的左子树 19.5无左子树 20.打印5 21.进入5的右子树 22.5无右子树 23.打印3 24.进入3的右子树68 25.进入6的左子树8 26.进入8的左子树 27.8无左子树 28.打印8 29.进入8的右子树 30.8无右子树 31.打印6 32.进入6的右子树 33.6无右子树
#include<iostream> #include<vector> using namespace std; //思路： //抓住本质 //对于每个子树的前序遍历，都是根左右的顺序!!! //对于每个子树的中序遍历，都是左根右的顺序!!! //对于每个子树，前序遍历的第一个值是根结点的值，利用该值将该子树的中序遍历结果再次分成左右两个新子树，并获得两个新子树的前序遍历和中序遍历 struct TreeNode { int value; TreeNode*left; TreeNode*right; TreeNode(int x = 0) :value(x), left(NULL), right(NULL) {} }; class Solution { public: TreeNode*ReConstructBinaryTree(vector<int>pre, vector<int>vin) { if (pre.size() == 0) return NULL; vector<int>left_vin_new, right_vin_new, left_pre_new, right_pre_new; TreeNode*head = new TreeNode(pre[0]); int root = 0; //找到中序遍历中的根结点的索引 for (int i = 0; i < vin.size(); i++) { if (vin[i] == pre[0]) { root = i; break; } } //根据中序遍历的根结点，获取新的左、右子树的中序遍历 for (int i = 0; i < root; i++) { left_vin_new.push_back(vin[i]); } for (int i = root + 1; i < vin.size(); i++) { right_vin_new.push_back(vin[i]); } //根据中序遍历的根结点，获取新的左、右子树的前序遍历 for (int i = 0; i < root; i++) { left_pre_new.push_back(pre[i + 1]);//前序遍历的第一个是根结点 } for (int i = root + 1; i < vin.size(); i++) { right_pre_new.push_back(pre[i]); } //递归 head->left = ReConstructBinaryTree(left_pre_new, left_vin_new); head->right = ReConstructBinaryTree(right_pre_new, right_vin_new); return head;//当前层递归结束，返回当前层的根结点，回到上一层的递归 } }; int main() { vector<int>pre = {1,2,4,7,3,5,6,8}; vector<int>vin = {4,7,2,1,5,3,8,6}; Solution solution; TreeNode*head = solution.ReConstructBinaryTree(pre, vin); cout << head->left->left->right->value << endl; system("pause"); return 0; }