算法题--重建二叉树
2022/11/4 3:24:59
本文主要是介绍算法题--重建二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
6
要求
时间限制:1秒 空间限制:32768K
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回
解题思路
解题的前提:两个序列中必须有一个中序序列
前(后)序序列用于提供根节点,根节点就是序列第一个元素(最后一个元素)
中序序列用于确定当前根节点的左右子树有哪些节点
如下图所示:
确定了左右子树有哪些元素之后就继续递归
代码
/* Definition for binary tree struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; */ class Solution { public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { int psize=pre.size(); int vsize=vin.size(); if(psize==0 || vsize==0 || psize != vsize) return NULL; return reBuildBinaryTreeCore(pre, 0, psize-1, vin, 0, vsize-1); } TreeNode* reBuildBinaryTreeCore(vector<int>& pre, int startIdxOfP, int endIdxOfP, vector<int>& vin, int startIdxOfV, int endIdxOfV) { int valOfRoot = pre[startIdxOfP]; TreeNode* root = new TreeNode(valOfRoot); if(startIdxOfP == endIdxOfP) { if(startIdxOfV == endIdxOfV) return root; else { cout << "无效输入" << endl; abort(); } } else { int idxOfRootInV = 0; for(idxOfRootInV = startIdxOfV;idxOfRootInV <= endIdxOfV && vin[idxOfRootInV] != valOfRoot;++idxOfRootInV) { } if(vin[idxOfRootInV] != valOfRoot) { cout << "无效输入" << endl; abort(); } int leftLength = idxOfRootInV - startIdxOfV; //左 if(startIdxOfV <= idxOfRootInV - 1) root->left = reBuildBinaryTreeCore(pre, startIdxOfP + 1, startIdxOfP + leftLength, vin, startIdxOfV, idxOfRootInV - 1); //右 if(idxOfRootInV + 1 <= endIdxOfV) root->right = reBuildBinaryTreeCore(pre, startIdxOfP + 1 + leftLength, endIdxOfP, vin, idxOfRootInV+1, endIdxOfV); } return root; } };
这篇关于算法题--重建二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署