当前位置: 首页> 健康> 知识 > LeetCode106 从中序与后序遍历序列构造二叉树

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

时间:2025/7/11 3:53:36来源:https://blog.csdn.net/daishabby2486/article/details/141183704 浏览次数:0次

前言

题目: 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);}
};
关键字:LeetCode106 从中序与后序遍历序列构造二叉树

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: