前言：

二叉樹刷題是有固定思維的，請移步

README】二叉樹刷題框架

文章目錄

• 前言：
• 從前序和中序遍歷構(gòu)建二叉樹
• • 思路
  • 代碼
  • 注意
• 從中序和后序遍歷構(gòu)建二叉樹
• • 思路
  • 代碼

從前序和中序遍歷構(gòu)建二叉樹

題目

點擊跳轉(zhuǎn)：LeetCode

思路

這道題體現(xiàn)的就是分治的思想，我們知道前序遍歷啊可以確定一個子樹的根節(jié)點，而中序遍歷可以根據(jù)根節(jié)點將一顆子樹再次分為左右子樹，所以只需分解完成一次，后面的過程就是遞歸過程

如下，首先根據(jù)前序確定這棵樹的根節(jié)點為A，然后根據(jù)中序遍歷確定A的左右子樹在中序中的范圍

下一步又分別確定了左右子樹的根節(jié)點為B和C

剩下的就是遞歸過程

代碼

class Solution { public:TreeNode* _buildTree(vector<int>& preorder,vector<int>& inorder,int& previ,int inbegin,int inend){if(inbegin>inend)//中序區(qū)間不存在，也就是該結(jié)點不存在左子樹return nullptr;int rooti=inbegin;//用rooti保存中序遍歷中root的位置while(rooti<=inend)//尋找{if(inorder[rooti]==preorder[previ])break;elserooti++;}TreeNode* root=new TreeNode(preorder[previ]);//依此時前序遍歷的第一個值創(chuàng)建一個結(jié)點++previ;//劃分區(qū)間，剩余的過程就是遞歸//即[inbegin,rooti-1]root[rooti+1,inend]root->left=_buildTree(preorder,inorder,previ,inbegin,rooti-1);root->right=_buildTree(preorder,inorder,previ,rooti+1,inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int previ=0;return _buildTree(preorder,inorder,previ,0,inorder.size()-1);} };

注意

上述代碼中有一個很重要的判斷

if(inbegin>inend)//中序區(qū)間不存在，也就是該結(jié)點不存在左子樹return nullptr;

這個判斷是為了防止中序遍歷區(qū)間不存在的情況，如下，下面的樹中結(jié)點A沒有左子樹，所以就會導(dǎo)致inbegin > inend

從中序和后序遍歷構(gòu)建二叉樹

題目

點擊跳轉(zhuǎn)：LeetCode

思路

和上一題思路一致，只不過需要注意的是，一定要先構(gòu)建右子樹然后構(gòu)建左子樹

代碼

class Solution { public:TreeNode* _buildTree(vector<int>& inorder,vector<int>& postorder,int& posti,int inbegin,int inend){if(inbegin>inend)//區(qū)間不存在return nullptr;int rooti=inbegin;while(rooti<=inend){if(inorder[rooti]==postorder[posti])break;elserooti++;}TreeNode* root=new TreeNode(postorder[posti]);--posti;root->right=_buildTree(inorder,postorder,posti,rooti+1,inend);root->left=_buildTree(inorder,postorder,posti,inbegin,rooti-1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int posti=postorder.size()-1;return _buildTree(inorder,postorder,posti,0,inorder.size()-1);} };

總結(jié)

以上是生活随笔為你收集整理的二叉树经典题之从前序和中序遍历构建二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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