建设企业网站e路护航,公司年会活动方案策划,电商seo是什么,房地产微网站给定两个整数数组 inorder 和 postorder #xff0c;其中 inorder 是二叉树的中序遍历#xff0c; postorder 是同一棵树的后序遍历#xff0c;请你构造并返回这颗 二叉树 。
思路一#xff1a;递归
struct TreeNode* createTreeNode(int val) {struct TreeNode* ret ma…给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。
思路一递归
struct TreeNode* createTreeNode(int val) {struct TreeNode* ret malloc(sizeof(struct TreeNode));ret-val val;ret-left ret-right NULL;return ret;
}struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {if (postorderSize 0) {return NULL;}struct TreeNode* root createTreeNode(postorder[postorderSize - 1]);struct TreeNode** s malloc(sizeof(struct TreeNode*) * 10001);int top 0;s[top] root;int inorderIndex inorderSize - 1;for (int i postorderSize - 2; i 0; i--) {int postorderVal postorder[i];struct TreeNode* node s[top - 1];if (node-val ! inorder[inorderIndex]) {node-right createTreeNode(postorderVal);s[top] node-right;} else {while (top 0 s[top - 1]-val inorder[inorderIndex]) {node s[--top];inorderIndex--;}node-left createTreeNode(postorderVal);s[top] node-left;}}return root;
}
分析
本题要利用二叉树的中序遍历和后序遍历来确定二叉树即可不断创建新二叉树将后序遍历的右子树赋值给新二叉树不断创建等栈顶为根节点的位置时再将左子树创建为新二叉树最后输出
总结:
本题考察对二叉树的应用先找到根节点不断添加二叉树即可解决
