二叉搜索树和二叉判定树_判断二叉树是否为二叉排序树的算法

二叉树LeetCode经典题目 　　1，二叉树理论 　　这里就简单的说一下二叉树的种类 　　满二叉树：如果一颗二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵树为满二叉树。

　　完全二叉树：最底层节点可能没有填满，其余每层节点都达到最大值，并且最下面一层节点都集中在该层最左边的位置。 　　二叉搜索树：BST左子树的值小于根节点，右子树的值大于根节点，且左子树和右子树也是二叉搜索树。

　　平衡二叉树：它是一棵空树或左右两个子树的高度绝对差不超过1，并且左右两个都是一颗平衡二叉树

　　二叉树的遍历方式： 　　前序遍历，中序遍历，后序遍历 　　这里我来简单的说一下，二叉搜索树的中序遍历是一个递增序列，如果想从叶子节点进行操作，那么后序遍历是一个很好的操作，后序遍历是先访问叶子节点再访问根节点的。前序遍历一般是用来遍历二叉树的，从上到下依次操作。 　　关于二叉树的解题思路，最重要的是递归，要把递归思想搞清楚，递归三部曲：确定递归函数的参数和返回值，确定终止条件，确定单层递归的逻辑 　　2，迭代法进行前序遍历 　　前序遍历是中左右，那么先将根节点放入栈中，然后再放右孩子，然后再放左孩子，这里我们要记住，从栈中取出的素是从上到下，取出左孩子后看他是否为空，不为空就继续添加。







　　核心代码为： 　　3，迭代法进行中序遍历 　　中序遍历是左中右，所以是先访问二叉树的根节点，判断有没有左子树，有，当前节点入栈，然后更新当前节点值为左子树，然后重复上述操作，当前节点如果为空的话就取出栈顶素，输出值，并看是否有右子树，有的话就将右子树入栈，没有的话就继续取栈顶素。重复上述操作，核心代码为： 　　4，迭代法进行后序遍历 　　后序遍历是左右中那么我们只需要

　　核心代码为： 　　虽然上述写了那么多非递归的方法遍历二叉树，但是具体解题方法还是递归比较有思路和好解决，当然因人而异。 　　5，二叉树的层序遍历 　　为解决这种遍历方法，我们需要借用一个辅助队列来实现，队列先进先出，符合一层一层遍历的逻辑具体请看下图

　　核心代码为： 　　6，226 翻转二叉树

　　这一题是一道非常简单的题，我们知道交换两个数的值用一个中间值来进行交换，同理我们也可以运用这个思路将两个树的左右子树进行交换，这里要注意，左右子树交换完，那么左右子树的左右子树也要交换。于是我们就有以下代码 　　7，101 对称二叉树 　　给你一个二叉树的根节点root，检查他是否轴对称



　　同样，建立递归思路，递归三部曲走起，确定递归函数的含义就是判断这棵树是否是对称的，然后确定递归结束条件，判断左右子树是否都有节点，再看左右子树的值是否相等，之后操作判断左右子树的左右子树是否是对称的 　　8，104二叉树的最大深度 　　给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径数。

　　同样递归三部曲走起，一，确定函数的意义，这个递归函数的意义就是当前子树的最大深度；二，确定递归结束条件，当前节点为空返回0；三当前节点的操作，判断左子树的最大深度，右子树的最大深度，并从中找到一个最大的，并加上当前节点的深度1返回即可 　　9，111二叉树的最小深度 　　给定一个二叉树，找出其最小深度。 　　最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 　　说明：叶子节点是指没有子节点的节点。

　　这一题看着和上一题差不多，但是我们要看清，它的意思是到叶子节点的长度，而不是当前二叉树的最小深度；同理，递归三部曲走起，一确定该递归函数的意义，就是找到当前给定二叉树的最小深度；二，确定递归结束条件，如果当前节点为null的话，说明深度为0，到头了，返回0；三，对当前节点进行操作，如果当前节点没有左子树但有右子树，这时候我们只需要递归右子树即可，可能会有同学说，左子树没有不应该返回当前节点左右子树的最小深度，1嘛，为什么直接递归右子树了？这是因为，不是根节点到叶子节点的深度，所以不要搞错，要理解清题意。同理，右子树。同理，如果左右子树都不为空，那么就直接进行判断左右子树的最小深度，并加上当前节点的深度1. 　　10,222完全二叉树的节点个数 　　给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。 　　完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点

　　这一题非常简单，就让你求节点个数，你前序遍历也行，层序遍历也可，求出节点个数即可，即递归函数为左子树上的节点个数加上右子树上的节点个数然后再加1. 　　11，110平衡二叉树 　　给定一个二叉树，判断它是否是高度平衡的二叉树。 　　本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。



　　很明显这一题直接把题意告诉你了，确定递归函数的意义，这里我们要建立一个height函数帮助我们判断二叉树的深度和判断是否是平衡二叉树，不断的递归，当出现绝对值大于1的情况就返回false。 　　12，513找树左下角的值 　　给定一个二叉树的 根节点 ，请找出该二叉树的 最底层 最左边 节点的值。 　　假设二叉树中至少有一个节点。

　　根据题意，我们可以知道这是要让我们找到最左边的叶子的值，可是怎么判断最左边呢？即左子树和右子树谁的深度大，谁就有最左边叶子节点。于是直接递归三部曲，一判断递归函数的含义，找到当前子树的最左边节点；二判断递归函数的结束条件，为空，或者找到了叶子节点返回值。三，对当前节点进行操作，左子树深度大，找左子树右子树的深度大，找右子树。 　　13，从中序遍历与后序遍历构造二叉树 　　根据一棵树的中序遍历与后序遍历构造二叉树。

　　可能我说的不是很好理解，这里我搬来了官方的题解我觉得挺好，大家看一下 　　为了高效查找根节点素在中序遍历数组中的下标，我们选择创建哈希表来存储中序序列，即建立一个（素，下标）键值对的哈希表。 　　定义递归函数 helper(in_left, in_right) 表示当前递归到中序序列中当前子树的左右边界，递归入口为helper(0, n – 1) ： 　　如果 in_left > in_right，说明子树为空，返回空节点。 　　选择后序遍历的最后一个节点作为根节点。 　　利用哈希表 O(1)O(1) 查询当根节点在中序遍历中下标为 index。从 in_left 到 index – 1 属于左子树，从 index + 1 到 in_right 属于右子树。 　　根据后序遍历逻辑，递归创建右子树 helper(index + 1, in_right) 和左子树 helper(in_left, index – 1)。注意这里有需要先创建右子树，再创建左子树的依赖关系。可以理解为在后序遍历的数组中整个数组是先存储左子树的节点，再存储右子树的节点，最后存储根节点，如果按每次选择「后序遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树。 　　返回根节点 root。 　　14，98 验证二叉搜索树 　　给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 　　有效 二叉搜索树定义如下： 　　节点的左子树只包含 小于 当前节点的数。 　　节点的右子树只包含 大于 当前节点的数。 　　所有左子树和右子树自身必须也是二叉搜索树。



　　看到这个题目大家心里想，肯定很简单对吧，直接判断当前节点和左右子树节点的大小不久好了吗？这就打错特错了，如果当前节点的左节点的右节点比当前节点还大怎么办？可以上来就简单的判断吗，答案肯定是不行的。但是我们可以建立这样的思路，我们知道，二叉搜索树的左子树都是比当前节点小，右子树都是比当前节点大，于是我们可以建立一个范围，从上到下遍历节点，判断每一个节点是否都在我这个范围内，这里我举个例子吧，看上图，5这个节点你要确保它是否在负无穷到正无穷对不对，然后又到左子树了，这个时候我们就要知道，更新最大值，5，确定左子树1是否在负无穷到5这个范围内，很明显是在的。然后到右子树，更新区间5，到+∞，很明显4不是，就要返回false；但是这里我们假设一下它是对的假设4是7，然后更新，边界，[5 7]，然后又到3这个节点了，判断是否在这个范围内。不在返回。就是说，有点像逼近的思想，比大的小，比小的要大。 　　当然我们也知道，二叉搜索树的中序遍历是一个递增序列，你也可以判断它的中序遍历结果是不是一个递增序列。 　　15，236二叉树的最近公共祖先 　　给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 　　百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

　　这一题可能会有人想，我从叶子节点不断的判断多好。对的，我们知道后序遍历是先处理叶子节点的，于是我们后序遍历处理叶子节点，这个大思想有了，然后递归三部曲走起，一，确定函数的意义，函数的意义是找到两个节点的最近公共祖先；二，递归结束条件，找到了节点，或者为null返回。三，处理节点，看右子树有没有我要找的节点，左子树有没有我要找的节点，然后如果左子树有，但右子树没有则返回左子树；同理右子树。如果两边都有我要找的节点，直接返回自身，说明自身是它们找的最近公共祖先。(这里要注意，它是一层一层不断地向上传递的。所谓的返回左子树，其实可能是左子树里面的某一个节点。这个节点是最近的。) 　　16，701二叉搜索树中的插入操作 　　给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。 　　注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

　　这题比较简单，直接根据题意进行操作即可，不断地从根节点开始，看它比他大还是比他小，然后一找到空的就直接比较即可 　　17，450删除二叉搜索树中的节点 　　给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。 　　一般来说，删除节点可分为两个步骤： 　　首先找到需要删除的节点； 　　如果找到了，删除它。

　　我们根据题意，我们可以看出，它要我们删除节点，于是这一题就变成了两个简单难度的题 　　1，找到这个节点 　　2，删除这个节点，并将左子树和右子树合并 　　18，669修建二叉搜索树给你二叉搜索树的根节点 ，同时给定最小边界 和最大边界 。通过修剪二叉搜索树，使得所有节点的值在中。修剪树不应该改变保留在树中的素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。 　　所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

　　根据题意我们很好理解，就是让我们删除不在范围内的节点，于是这就变成了三个简单的题 　　1，存所有不在范围内的值 　　2，找到那个那个值的节点，然后删除 　　3，合并删除后的节点的左子树和右子树 　　19，1038把二叉搜索树转换成累加树 　　给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。 　　提醒一下，二叉搜索树满足下列约束条件： 　　节点的左子树仅包含键 小于 节点键的节点。 　　节点的右子树仅包含键 大于 节点键的节点。 　　左右子树也必须是二叉搜索树。

　　解题思路 　　根据题意，我们很简单能理解题目在说什么，就是把大于或等于它的节点加一块，我们建立以下思路 　　1，我们知道，二叉搜索树的中序遍历是递增的，所以我先把二叉搜索树的所有节点值都存下来 　　2，然后把利用map把每一个的下标存起来 　　3，再从新构造二叉树，找到比他大的那个下标，然后累加即可 　　20，总结涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点也就是根节点。求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。求二叉搜索树的属性，一定是中序了，利用有序性。最重要的是，一定要学会搞清递归三部曲，返回值、参数是什么即函数意义？终止条件是什么？单层逻辑是什么？ 　　码字不易，还望点个赞点个多多支持一下！后序我还会不断更新关于力扣题解有关的知识，感兴趣的小伙伴可以点个，我们一起进步！