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

[编程题]从中序与后序遍历序列构造二叉树

热度指数：5529 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树的中序与后序遍历结果，请你根据两个序列构造符合这两个序列的二叉树。

数据范围：二叉树的节点数满足 $1 \le n \le 1000 \$ ，节点上的值满足 $|val| \le 10^9 \$ ，保证节点的值各不相同

例如输入[2,1,4,3,5],[2,4,5,3,1]时，

根据中序遍历的结果[2,1,4,3,5]和后序遍历的结果[2,4,5,3,1]可构造出二叉树{1,2,3,#,#,4,5}，如下图所示：

示例1

输入

[1],[1]

输出

{1}

示例2

输入

[2,1,4,3,5],[2,4,5,3,1]

输出

{1,2,3,#,#,4,5}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

acetao

C语言代码实现：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param inorder int整型一维数组 中序遍历序列
 * @param inorderLen int inorder数组长度
 * @param postorder int整型一维数组 后序遍历序列
 * @param postorderLen int postorder数组长度
 * @return TreeNode类
 */
struct TreeNode* buildTree(int* inorder, int inorderLen, int* postorder, int postorderLen ) {
	// write code here
	if (inorderLen < 1 || postorderLen < 1)return NULL;
	struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
	root->val = postorder[postorderLen - 1];
	int* p = inorder;
	for (; p < inorder + inorderLen; p++) {
		if (*p == postorder[postorderLen - 1])
			break;
	}
	int k = p - inorder;	//左子树结点数量
	//递归构建左子树：中序开始位置inorder，后序开始位置postorder
	root->left = buildTree(inorder, k, postorder, k);

	//右子树结点数量inorderLen - k - 1
	//递归构建右子树：中序开始位置p+1，后序开始位置postorder+k
	root->right = buildTree(p + 1, inorderLen - k - 1, postorder + k, inorderLen - k - 1);
	return root;
}

//前序遍历
void preOrder(struct TreeNode* root) {
	if (root) {
		printf("%d ", root->val);
		preOrder(root->left);
		preOrder(root->right);
	}
}

int main(int argc, char *argv[])
{
	int inorder[] =   {2, 1, 4, 3, 5};
	int postorder[] = {2, 4, 5, 3, 1};
	int n = sizeof(inorder) / sizeof(int);
	struct TreeNode* root = buildTree(inorder, n, postorder, n);
	preOrder(root);
	printf("\n");

	return 0;
}

发表于 2023-10-15 18:53:49 回复(0)

פנטום

typedef struct TreeNode TreeNode;
TreeNode* tree(int* inorder, int inL,int inR, int* postorder, int postL,int postR);

struct TreeNode* buildTree(int* inorder, int inorderLen, int* postorder, int postorderLen ) {
    // write code here
    return tree(inorder,0,inorderLen-1,postorder,0,postorderLen-1);
    
}

//递归法构造
TreeNode* tree(int* inorder, int inL,int inR, int* postorder, int postL,int postR)
{
    if(postL>postR)
        return NULL;
    
    TreeNode* node = malloc(sizeof(TreeNode));
    node->val=postorder[postR];
    int pos = inL;
    while(pos<=inR && inorder[pos]!=node->val)
    {
        ++pos;
    }
    node->left = tree(inorder, inL, pos-1, postorder, postL, postL+pos-inL-1);
    node->right = tree(inorder, pos+1, inR, postorder, postL+pos-inL, postR-1);
    return node;
}

发表于 2022-03-17 20:54:54 回复(0)