題目描述

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

中等

1.1K

相關(guān)企業(yè)

給定兩個(gè)整數(shù)數(shù)組?inorder?和?postorder?，其中?inorder?是二叉樹的中序遍歷，?postorder?是同一棵樹的后序遍歷，請(qǐng)你構(gòu)造并返回這顆?二叉樹?。

示例 1:

輸入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
輸出：[3,9,20,null,null,15,7]

示例 2:

輸入：inorder = [-1], postorder = [-1]
輸出：[-1]

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder?和?postorder?都由?不同?的值組成
• postorder?中每一個(gè)值都在?inorder?中
• inorder?保證是樹的中序遍歷
• postorder?保證是樹的后序遍歷

思路講解

后續(xù)遍歷：左 右 中

中序遍歷：左 中 右

假設(shè)沒有重復(fù)值的節(jié)點(diǎn) 如果有那就不會(huì)是種二叉樹 你可以將重復(fù)節(jié)點(diǎn)挨個(gè)遍歷 依次確定所有二叉樹

那么后續(xù)排序就可以確定這顆二叉樹的根節(jié)點(diǎn) 再在中序排序中找到該值（根節(jié)點(diǎn)）

將中序遍歷分為三部分 左子樹的中序遍歷 根節(jié)點(diǎn) 右子樹的中序遍歷?

將后序遍歷分為三部分 左子樹的后續(xù)遍歷 右子樹的后續(xù)遍歷 根節(jié)點(diǎn)

經(jīng)過上面的處理 不能形成一顆完整的二叉樹 因?yàn)槔锩嬗凶笥易訕溥€沒有確定其根節(jié)點(diǎn)

那么就要再進(jìn)行上 面的操作 直到將左右子樹全部確定完畢?

需要遞歸進(jìn)行處理 也可以模擬遞歸 用棧去模擬遞歸?

結(jié)合上面思路先大致想一想遞歸代碼的實(shí)現(xiàn)

代碼部分處理

/**//樹的節(jié)點(diǎn)* Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* func1(vector<int>& inorder,vector<int>& postorder)//遞歸{//postorder.size()==inorder.size()if(postorder.size()==0){return nullptr;}int val = postorder[postorder.size()-1];TreeNode* root = new TreeNode(val);//創(chuàng)建節(jié)點(diǎn)int index = 0;//尋找中序的根節(jié)點(diǎn)for(;index<inorder.size();index++){if(inorder[index]==val){break;}}//postorder.size()==inorder.size()if(postorder.size()==1){return root;}postorder.resize(postorder.size()-1);//左閉右開區(qū)間 區(qū)間端點(diǎn)就是函數(shù)參數(shù)vector<int> leftinorder(inorder.begin(),inorder.begin()+index);vector<int> rightinorder(inorder.begin()+index+1/*+1就是將中序的根節(jié)點(diǎn)舍棄掉*/,inorder.end());vector<int> leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());vector<int> rightpostorder(postorder.begin()+leftinorder.size(),postorder.end());//遞歸調(diào)用root->left=func1(leftinorder,leftpostorder);root->right=func1(rightinorder,rightpostorder);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size()==0||postorder.size()==0)//特殊條件的判斷{return nullptr;}return func1(inorder,postorder);}
};

遞歸調(diào)用部分：

需要對(duì)遞歸有一點(diǎn)了解 不然你就在紙上走讀代碼 去畫遞歸展開圖

調(diào)用左樹就執(zhí)行到底之后再進(jìn)左樹調(diào)用中的右樹調(diào)用 再進(jìn)右樹調(diào)用還是先執(zhí)行左樹調(diào)用再執(zhí)行右樹調(diào)用 因?yàn)樽髽湔{(diào)用在右樹調(diào)用的前面