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;
}