您的位置:首页 > 游戏 > 手游 > leetcode106.从中序与后序遍历序列构造二叉树、leetcode105.从前序与中序遍历序列构造二叉树

leetcode106.从中序与后序遍历序列构造二叉树、leetcode105.从前序与中序遍历序列构造二叉树

2024/10/14 11:21:19 来源:https://blog.csdn.net/qq_45721938/article/details/140557963  浏览:    关键词:leetcode106.从中序与后序遍历序列构造二叉树、leetcode105.从前序与中序遍历序列构造二叉树

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

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
示例 1:
在这里插入图片描述
输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

示例 2:
输入:inorder = [-1], postorder = [-1]
输出:[-1]

解题思路

1、后序数组为0,空节点
2、后序数组最后一个元素为根节点
3、寻找根节点在中序数组位置作切割点
4、切中序数组
5、切后序数组
6、递归处理左区间右区间

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {if(!inorderSize) return NULL;struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));if (node == NULL) {// 处理内存分配失败return NULL;}node->val=postorder[postorderSize-1];int index;for (index = 0; index < inorderSize; index++) {if(inorder[index] == postorder[postorderSize-1]) {break;}}int rightSize=inorderSize-index-1;node->left=buildTree(inorder,index,postorder,index);//左闭右开node->right=buildTree(inorder+index+1,rightSize,postorder + index, rightSize);return node;
}

leetcode105.从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

示例 1:
在这里插入图片描述
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]

解题思路

1、前序数组为0,空节点
2、前序数组第一个元素为根节点
3、寻找根节点在中序数组位置作切割点
4、切中序数组
5、切前序数组
6、递归处理左区间右区间

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {if(!inorderSize) return NULL;struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));if (node == NULL) {// 处理内存分配失败return NULL;}node->val=preorder[0];int index;for (index = 0; index < inorderSize; index++) {if(inorder[index] == preorder[0]) {break;}}int rightSize=inorderSize-index-1;node->left=buildTree(preorder+1,index,inorder,index);//左闭右开node->right=buildTree(preorder+index+1,rightSize,inorder+index+1,rightSize);return node;
}

版权声明:

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

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