樟木头镇仿做网站,网站收录最好的方法,北京网站优化wyhseo,成品ppt的网站免费直播有哪些从前序与中序遍历序列构造二叉树 题目思路分析代码代码讲解 题目 思路分析 我们可以通过递归实现的二叉树构建函数。它根据给定的先序遍历序列和中序遍历序列构建一棵二叉树#xff0c;并返回根节点。可以创建一个_build 函数#xff0c;该函数负责构建二叉树的节点#xff… 从前序与中序遍历序列构造二叉树 题目思路分析代码代码讲解 题目 思路分析 我们可以通过递归实现的二叉树构建函数。它根据给定的先序遍历序列和中序遍历序列构建一棵二叉树并返回根节点。可以创建一个_build 函数该函数负责构建二叉树的节点通过分割先序遍历序列和中序遍历序列并递归构建左子树和右子树来完成整个二叉树的构建过程。最终buildTree 函数调用 _build 函数并返回构建的二叉树的根节点。
代码
class Solution {
public:TreeNode* _build(vectorint preorder, vectorint inorder, int peri, int begin, int end) {// 如果开始索引大于结束索引则返回空指针表示当前子树为空if (begin end) {return nullptr;}int rooti 0;// 在中序遍历序列中找到当前根节点的索引while (rooti end) {if (inorder[rooti] preorder[peri]) {break;}rooti;}// 创建当前根节点TreeNode* root new TreeNode(preorder[peri]);// 构建左子树// 左子树的先序遍历序列为 [begin, rooti-1]// 左子树的中序遍历序列为 [begin, rooti-1]root-left _build(preorder, inorder, peri, begin, rooti-1);// 构建右子树// 右子树的先序遍历序列为 [rooti1, end]// 右子树的中序遍历序列为 [rooti1, end]root-right _build(preorder, inorder, peri, rooti1, end);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i 0;// 调用内部函数 _build 构建二叉树// 初始时 peri 为 0表示从先序遍历序列的第一个元素开始构建// 根据先序遍历序列和中序遍历序列构建二叉树并返回根节点TreeNode* root _build(preorder, inorder, i, 0, preorder.size()-1);return root;}
};代码讲解
首先判断起始索引 begin 是否大于结束索引 end如果是则说明当前子树为空返回空指针。
在中序遍历序列 inorder 中找到当前根节点的索引 rooti该索引表示根节点在中序遍历中的位置。在循环中不断遍历中序遍历序列直到找到与先序遍历序列 preorder[peri] 相等的值。找到后rooti 就是根节点的索引。
创建当前根节点节点的值为 preorder[peri]。
根据先序遍历序列和中序遍历序列的特性可以将当前子树分为左子树和右子树。左子树的先序遍历序列为 preorder[begin, rooti-1]左子树的中序遍历序列为 inorder[begin, rooti-1]。右子树的先序遍历序列为 preorder[rooti1, end]右子树的中序遍历序列为 inorder[rooti1, end]。
递归调用 _build 函数分别构建左子树和右子树并将返回的根节点设置为当前根节点的左孩子和右孩子。
返回当前根节点。 总结 在 buildTree 函数中首先定义了一个变量 i初始值为 0作为 _build 函数中 peri 的初始值。然后调用 _build 函数传入先序遍历序列 preorder、中序遍历序列 inorder、i、0 和 preorder.size()-1即整个序列的起始和结束索引。最后返回构建的二叉树的根节点。
