链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/by-xun-ge-v-tklv/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
解题思路
思路还是比较好想,但是细节方面需要好好处理,思路和前序构造一模一样
构造二叉树,递归无疑是比较好的方法
对于下标处理到达要不要+1或者-1,最简单的方法就是代一个具体的值,算一下就知道了
一共如下几步:
小细节:具体实现可以用数组下标代替数组中元素具体数目,方便操作
具体实现看代码,注释超级详细
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * struct TreeNode *left;
- * struct TreeNode *right;
- * };
- */
- struct TreeNode * dfs(int * inorder, int i_left, int i_right, int * postorder, int p_left, int p_right)
- {
- if(i_left > i_right)//数组为0
- {
- return NULL;
- }
- struct TreeNode * root = malloc(sizeof(struct TreeNode));//构造节点,并初始化
- root->val = postorder[p_right];
- root->left = NULL;
- root->right = NULL;
- for(int i = i_left; i <= i_right; i++)//切割中序数组
- {
- if(inorder[i] == postorder[p_right])//找到了切割点
- {
- root->left = dfs(inorder, i_left, i-1, postorder, p_left, p_left+ i-1-i_left);
- root->right = dfs(inorder, i+1, i_right, postorder, p_left+ i-i_left, p_right-1);//直接根据中序数组切割点的元素个数,推导后序数组的切割点
- break;
- }
- }
- return root;
- }
-
- struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
- return dfs(inorder, 0, inorderSize-1, postorder, 0, postorderSize-1);//递归构造
- }
-
- 作者:xun-ge-v
- 链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/by-xun-ge-v-tklv/
- 来源:力扣(LeetCode)
- 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。