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