LeetCode106 从中序与后序遍历序列构造二叉树

前言

题目： 106. 从中序与后序遍历序列构造二叉树
文档： 代码随想录——从中序与后序遍历序列构造二叉树
编程语言： C++
解题状态： 完全不会…

思路

注意中序遍历和后序遍历的特点，后序遍历负责提供中间节点，中序遍历负责区分左右子树，依次遍历即可。

代码

/*** 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 {
private:TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {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.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;}public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;return traversal(inorder, postorder);}
};