本文主要是介绍177.二叉树:从前序与中序遍历序列构造二叉树(力扣),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码解决
/*** 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* traversal(vector<int>& preorder, int preorderBegin, int preorderEnd, vector<int>& inorder, int inorderBegin, int inorderEnd) {// 如果前序遍历序列为空,返回空指针if (preorderBegin == preorderEnd) return nullptr;// 获取前序遍历序列的第一个值作为当前子树的根节点值int rootVal = preorder[preorderBegin];TreeNode* root = new TreeNode(rootVal);// 如果前序遍历序列只有一个值,返回根节点if (preorder.size() == 1) return root;// 在中序遍历序列中找到根节点值的位置int delimiterIndex;for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {if (inorder[delimiterIndex] == rootVal)break;}// 划分左子树和右子树的中序遍历序列int leftInorderBegin = inorderBegin;int leftInorderEnd = delimiterIndex;int rightInorderBegin = delimiterIndex + 1;int rightInorderEnd = inorderEnd;// 划分左子树和右子树的前序遍历序列int leftPreorderBegin = preorderBegin + 1;int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin;int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);int rightPreorderEnd = preorderEnd;// 递归构建左子树和右子树root->left = traversal(preorder, leftPreorderBegin, leftPreorderEnd, inorder, leftInorderBegin, leftInorderEnd);root->right = traversal(preorder, rightPreorderBegin, rightPreorderEnd, inorder, rightInorderBegin, rightInorderEnd);// 返回构建好的根节点return root;}// 主函数,从前序和中序遍历序列中构建二叉树TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {// 如果中序或前序遍历序列为空,返回空指针if (inorder.size() == 0 || preorder.size() == 0) return nullptr;// 参数坚持左闭右开的原则return traversal(preorder, 0, preorder.size(), inorder, 0, inorder.size());} };
- 定义一个递归函数
traversal
,它接受前序遍历序列、前序遍历序列的起始和结束索引、中序遍历序列、中序遍历序列的起始和结束索引作为参数。- 首先检查前序遍历序列是否为空,如果是,返回空指针。
- 获取前序遍历序列的第一个值,这个值就是当前子树的根节点的值。
- 在中序遍历序列中找到根节点值的位置,并将其作为分隔点,将中序遍历序列划分为左子树和右子树的中序遍历序列。
- 同样地,将前序遍历序列划分为左子树和右子树的前序遍历序列。
- 递归地调用
traversal
函数来构建左子树和右子树。- 返回构建好的根节点。
- 在
buildTree
函数中,首先检查中序或前序遍历序列是否为空,如果是,返回空指针。然后调用traversal
函数来构建二叉树。这个算法的时间复杂度是 O(n),因为每个节点都会被访问一次,其中 n 是树中节点的数量。空间复杂度也是 O(n),因为需要存储递归调用的栈。
这篇关于177.二叉树:从前序与中序遍历序列构造二叉树(力扣)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!