從中序與后序遍歷序列構(gòu)造二叉樹

根據(jù)一棵樹的中序遍歷與后序遍歷構(gòu)造二叉樹。

注意:
你可以假設(shè)樹中沒有重復(fù)的元素。

例如，給出

中序遍歷 inorder = [9,3,15,20,7] 后序遍歷 postorder = [9,15,7,20,3]

返回如下的二叉樹：

3/ \9 20/ \15 7

思路： 根據(jù)構(gòu)造二叉樹的流程，中序遍歷的訪問順序?yàn)樽?中-右；后序遍歷的方位順序?yàn)樽?右-中。

后序最后一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，在中序列表中查找根節(jié)點(diǎn)值

將中序列表分割成左子樹中序列表和右子樹中序列表

因?yàn)閷τ谕瑯拥臉渲行蚝秃笮蛄斜黹L度相同，所以根據(jù)左子樹中序列表和右子樹中序列表的長度將后序列表分割成左子樹后序和右子樹后序

對左子樹根節(jié)點(diǎn)，右子樹根節(jié)點(diǎn)遞歸調(diào)用

返回根節(jié)點(diǎn)

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n=inorder.size();if(n>0){TreeNode* root=new TreeNode(postorder[n-1]);vector<int>::iterator it=find(inorder.begin(),inorder.end(),postorder[n-1]);vector<int> il,ir,pl,pr;il.assign(inorder.begin(),it);ir.assign(it+1,inorder.end());int l,r;l=il.size();r=ir.size();//中序后序遍歷長度相等pl.assign(postorder.begin(),postorder.begin()+l);pr.assign(postorder.begin()+l,postorder.end());root->left=buildTree(il,pl);root->right=buildTree(ir,pr);return root;}else return NULL; }

從前序與中序遍歷序列構(gòu)造二叉樹

根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。

注意:
你可以假設(shè)樹中沒有重復(fù)的元素。

例如，給出

前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7]

返回如下的二叉樹：

3/ \9 20/ \15 7

思路：
和中序后序構(gòu)造思路基本一致
根據(jù)構(gòu)造二叉樹的流程，前序遍歷的訪問順序?yàn)橹?左-右，中序遍歷的訪問順序?yàn)樽?中-右。

前序第一一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，在中序列表中查找根節(jié)點(diǎn)值

將中序列表分割成左子樹中序列表和右子樹中序列表

因?yàn)閷τ谕瑯拥臉渲行蚝颓靶蛄斜黹L度相同，所以根據(jù)左子樹中序列表和右子樹中序列表的長度將前序列表分割成左子樹前序和右子樹前序

對左子樹根節(jié)點(diǎn)，右子樹根節(jié)點(diǎn)遞歸調(diào)用

返回根節(jié)點(diǎn)

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n=preorder.size();if(n>0){TreeNode* root=new TreeNode(preorder[0]);vector<int>::iterator it=find(inorder.begin(),inorder.end(),preorder[0]);vector<int> il,ir,pl,pr;il.assign(inorder.begin(),it);ir.assign(it+1,inorder.end());int l,r;l=il.size();r=ir.size();//中序前序遍歷長度相等pl.assign(preorder.begin()+1,preorder.begin()+l+1);pr.assign(preorder.begin()+l+1,preorder.end());root->left=buildTree(pl,il);root->right=buildTree(pr,ir);return root;}else return NULL; }

轉(zhuǎn)載于:https://www.cnblogs.com/wendyy/p/9332633.html

總結(jié)

以上是生活随笔為你收集整理的[leetcode]从中序与后序/前序遍历序列构造二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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