我是靠谱客的博主 细腻百合，最近开发中收集的这篇文章主要介绍根据二叉树的先序和中序构造二叉树的二叉链表_LeetCode刷题总结之二叉树的构建算法-一道题13种解法...，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
前言
最近开始刷到一些二叉树的构建的算法题，挺有意思的，打算总结一下。这里总结的都是确定二叉树的构造算法题，可能有多个构造结果的算法题就没考虑。
从构造目标上来看，这里讨论的算法题可以分为两种：
- 二叉树的构造
- 二叉搜索树（BST）的构造
从构造条件上来看，这里讨论的算法题也可以分为两种：
- 不含重复数值节点的二叉树的构造
- 含重复数值节点的二叉树的构造
1.从前序与中序遍历以及中序和后序遍历构造二叉树
这2个题目分别为：
- LeetCode.105 从前序与中序遍历序列构造二叉树，中等难度
- LeetCode.106 从中序与后序遍历序列构造二叉树，中等难度
1.1 解题方法
首先，按之前我们给分类条件给这两种题目一个定性：它们都是一个不含重复节点的二叉树构造算法题。这2个题目的思路和做法都是一样的：
- 首先从先序/后序序列中找到根节点，根据根节点将中序序列分为左子树和右子树。
- 递归地对左子树和右子树进行二叉树的构造。
思路其实是比较好想的，如果你在面试中遇到了这2个题目，那其实考察的编码的基本功了。虽然比较好想，但是一次把代码写出来且保证AC还是有一定难度的。
1.2 复杂度分析
时间复杂度: O(n)，由于每次递归我们的inorder和preorder的总数都会减1，因此我们要递归n次。 空间复杂度: O(n)，递归n次，系统调用栈的深度为n。
1.3 Show the code
最后
以上就是细腻百合为你收集整理的根据二叉树的先序和中序构造二叉树的二叉链表_LeetCode刷题总结之二叉树的构建算法-一道题13种解法...的全部内容，希望文章能够帮你解决根据二叉树的先序和中序构造二叉树的二叉链表_LeetCode刷题总结之二叉树的构建算法-一道题13种解法...所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复