一、题意
二、思考过程
思路：以 后序数组的最后一个元素为切割点，先切割中序数组，根据中序数组，反过来切割后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
class Solution { private: 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; } // 第四步：切割中序数组 // 左闭右开区间：[0, delimiterIndex) vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex); // [delimiterIndex + 1, end) vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() ); // postorder 舍弃末尾元素;resize()能够删除多余的末尾元素 postorder.resize(postorder.size() - 1); // 第五步：切割后序数组 // 依然左闭右开，注意这里使用了左中序数组大小作为切割点 // [0, leftInorder.size) vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size()); // [leftInorder.size(), end) 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); } }; ; return traversal(inorder, postorder); } };
三、从前序与中序遍历构造二叉树
class Solution { private: TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) { if (preorderBegin == preorderEnd) return NULL; int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0 TreeNode* root = new TreeNode(rootValue); if (preorderEnd - preorderBegin == 1) return root; int delimiterIndex; for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) { if (inorder[delimiterIndex] == rootValue) break; } // 切割中序数组 // 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd) int leftInorderBegin = inorderBegin; int leftInorderEnd = delimiterIndex; // 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd) int rightInorderBegin = delimiterIndex + 1; int rightInorderEnd = inorderEnd; // 切割前序数组 // 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd) int leftPreorderBegin = preorderBegin + 1; int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size // 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd) int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin); int rightPreorderEnd = preorderEnd; root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, preorder, leftPreorderBegin, leftPreorderEnd); root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd); return root; } public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (inorder.size() == 0 || preorder.size() == 0) return NULL; // 参数坚持左闭右开的原则 return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size()); } };
