視頻講解：https://www.bilibili.com/video/BV1vW4y1i7dn/?vd_source=a935eaede74a204ec74fd041b917810c
文檔講解：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
力扣題目：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
通過中序遍歷與后續遍歷來構造二叉樹要注意的是
- 先確定根節點，也就是后序遍歷的最后一個元素
- 根據根節點的值將中序遍歷分為左中序和右中序，左中序就是左子樹，右中序就是右子樹。
- 根據左中序的長度可以在后序遍歷中找到左后序的長度，同時得到右后序的長度，在其找出根節點，循環切割中序遍歷和后序遍歷
- 當切割的數組長度為1時就是最后一個根節點了，也就是遍歷到了葉子節點，返回root
- 如果便利的數組長度為0，則證明是空樹，直接返回空即可。
class Solution {
public:
TreeNode *traversal(vector<int>&inorder,vector<int>&postorder)
{//如果遍歷數組長度為0，則為空樹if(postorder.size()==0) return NULL;//找到后序遍歷最后一個元素，就是當前的中間節點int rootValue = postorder[postorder.size()-1];TreeNode *root = new TreeNode(rootValue);//葉子節點if(postorder.size() == 1) return root;//找切割點int delimiterIndex;for(delimiterIndex=0; delimiterIndex< inorder.size();delimiterIndex++){if(inorder[delimiterIndex] == rootValue) break;}//切割 切成左中序和右中序vector<int > leftInorder(inorder.begin(),inorder.begin()+delimiterIndex);vector<int> rightInorder(inorder.begin()+delimiterIndex+1,inorder.end());//postorder舍棄末尾元素postorder.resize(postorder.size()-1);//切割后序數組 左后序 右后序vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());//開始遞歸root->left=traversal(leftInorder,leftPostorder);root->right=traversal(rightInorder,rightPostorder);//返回值return root;
}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {//如果兩數組都為空，則樹為空if(inorder.size()==0 &&postorder.size()==0) return NULL;return traversal(inorder,postorder);}
};
)
)
