題目描述

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

思路

回顧三種經(jīng)典的遍歷：來自鄧俊輝的數(shù)據(jù)結(jié)構(gòu)dscpp-3rd-第五章二叉樹。

VLR

LRV

LVR

很簡單，遞歸即可。

注意遞歸出口和二叉樹索引的邊界。

/*** 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* build(vector<int> pre, int p_left, int p_right, vector<int> vin, int v_left, int v_right){if(p_left > p_right || v_left > v_right) return nullptr;TreeNode* root = new TreeNode(pre[p_left]);//建立rootfor(int i=v_left; i<=v_right; i++){if(vin[i] == root->val){root->left = build(pre, p_left+1, p_left+i-v_left, vin, v_left, i-1);//建立左子樹root->right = build(pre, p_left+i-v_left+1, p_right, vin, i+1, v_right);break;}}return root;}TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {return build(pre, 0, pre.size()-1, vin, 0, vin.size()-1);} };

總結(jié)

以上是生活随笔為你收集整理的二叉树的建立与遍历_51、二叉树遍历-重建二叉树JZ4的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。