背景树是一种常见的数据结构，应用场景非常多，也是面试中的常客。例如：树遍历、分层打印、将数据扁平化成树等等。这就需要我们对树的数据结构有一个基本的了解。今天我们再回顾一下这个数据结构。今天的课文内容主要包括：树二叉搜索树实战题目树在说树之前，我们先来回顾一下链表。事实上，链表、树和图都有一些联系。先看一个单向链表的示意图：每个节点都有一个value和一个next指向后面的节点，一路向后，形成一条链。这种结构非常方便，但也有一定的局限性。比如你想访问中间的某个节点，或者倒数第二个节点，你只能从头开始一个一个的去查，效率不高。为了解决这类问题，出现了很多方法，比如双向链表，每个节点不仅有一个后继节点，还有一个前驱节点。其实再观察一下，不难发现，如果每个节点都有两个next，会发生什么？变成我们所说的树。这是一个普通的二叉树结构，每个节点都有两个next指针，分别是左孩子和右孩子。二叉树的一种代码表示：这个特殊链表的第一个节点就是我们所说的树的根节点。树也是分层的。所谓层，就是离根节点的距离，如上图所示。如果每个节点都有两个子节点，则二叉树是一棵完整的二叉树。再看一看，如果这个节点还能指向根节点或者其他节点，这棵树会变成什么样子呢？没错，就变成了图片。我们生活中类似图的案例还有很多，比如你想去哪里，怎么走最短等等。简要总结：链表是一种特殊的树。树是一种特殊的图。二叉搜索树是一种特殊类型的二叉树。它可以是一棵空树，也可以是一棵二叉树，具有以下性质：左子树中所有节点的值都小于其根节点的值，右子树中所有节点的值均大于其根节点节点值的左右子树都是合法的二叉搜索树。比如：左孩子上的节点都小于27，后孩子上的节点都大于27。这种结构的好处是，比如我们要找一个元素的时候，只需要将其与根进行比较。如果它大于根，它在右子树中，如果它小于它在左子树中。每次搜索可以减少一半的数据量。与链表相比，找一个元素，链表是O(N)，而二叉查找树每次减半，变成O(log2(N))，效率提高了。最后，给出一张老式的对比图：在最坏的情况下，二叉查找树会退化为O(N)。比如只有右子树，没有左子树，就是一个长链。为了改善这种情况，后来发展了各种树，比如下面的红黑树SplayTreeAVLTree这三种也叫平衡二叉搜索树。在最坏的情况下，他们也可以保持O(log(n))的时间复杂度。在Java和C++的标准库中，二叉搜索树是用红黑树实现的。对红黑树感兴趣的同学可以看看维基百科：https://zh.wikipedia.org/wiki...理论说完了，下面进入实战。实用题二叉搜索树的验证这是leetcode的第98题，中等难度。给定一棵二叉树，判断它是否是一棵有效的二叉搜索树。假设一棵二叉搜索树具有以下特点：节点的左子树只包含小于当前节点的数字。节点的右子树仅包含大于当前节点的数字。所有的左子树和右子树本身必须是二叉搜索树。示例1：输入：2/\13输出：true示例2：输入：5/\14/\36输出：false解释：输入为：[5,1,4,null,null,3,6].根节点的值为5，但其右子节点的值为4。我用了三种方案，下面一一看。解法一：利用升序特征观察二叉查找树，不难发现，如果是合法的二分查找数，一定是左节点<根节点<右节点，所以得到的中序遍历一定是一个升序，可以这样验证。简单回顾一下二叉树的遍历：比如这棵树的中序遍历结果为：10141927313542那么利用升序特征，可以得到第一个解：varisValidBST=function(root){变量堆栈=[];//中序遍历函数dfs(root){if(!root)return;root.left&&dfs(root.left)root&&stack.push(root.val)root.right&&dfs(root.right)}dfs(root)for(vari=0;i=stack[i+1])返回false}returntrue;};不难发现，左节点<根节点<右节点，根节点的值一定夹在左右节点的值之间，如果不在这个范围内，肯定是不合法的。所以，按照这个思路，我们可以得到解法二。//空树也是合法的if(root.val<=min||root.val>=max)returnfalse;//不在范围内，不合法returnisValidBSTHelper(root.left,min,root.val)&&isValidBSTHelper(root.right,root.val,max);//数据减半，继续判断}returnisValidBSTHelper(root,-Infinity,Infinity)}这个方案也很好理解。方案三：利用特征第三个方案来自网友，也是利用了尺寸的特征。即：任意一个节点的值都必须大于其左子树最右边的节点；同时，它必须小于右子树的最左边的节点。从根节点开始检查，不满足则返回false。代码实现：varisValidBST=function(root){functiondfs(root){if(root==null)returntrueif(root.left){if(root.left.val>=root.val)returnfalseletrightest=getRightest(root.left)if(rightest&&rightest.val>=root.val)返回false}if(root.right){if(root.right.val<=root.val)returnfalseletleftest=getLeftest(root.right)if(leftest&&leftest.val<=root.val)returnfalse}returndfs(root.left)&&dfs(root.right)}functiongetRightest(node){while(node&&node.right)node=node.right返回节点}functiongetLeftest(node){while(node&&node.left)node=node.left返回节点}returndfs(root)};代码有点繁琐，理解思路即可。二叉搜索树的最近共同祖先是leetcode235。给定一棵二叉搜索树，找到树中两个指定节点的最近共同祖先。百度百科对最近共同祖先的定义是：“对于有根树T的两个节点p和q，最近共同祖先表示为节点x。满足x是p和q的祖先，深度为x尽可能大（一个节点也可以是它自己的祖先。例如，给定以下二叉搜索树：root=[6,2,8,0,4,7,9,null,null,3,5]示例1：输入：root=[6,2,8,0,4,7,9,null,null,3,5],p=2,q=8输出：6解释：节点的最近共同祖先2和8是6。示例2：输入：root=[6,2,8,0,4,7,9,null,null,3,5],p=2,q=4输出：2解释：The最近的节点2和节点4的共同祖先是2，因为根据定义，最近的共同祖先节点可以是节点本身。解释：所有节点的值都是唯一的。p，q是不同的节点，都存在在给定的二叉搜索树中，这道题我用了两种解法解法一：递归递归的思想也很简单：如果p，q都小于root，则说明解在左子树。如果p,q都大于root，说明解在右子树中。如果一个比根大，比根小一个，那么根就是最近的共同祖先。按照这个思路，实现代码：varlowestCommonAncestor=function(root,p,q){//p,q都小于root，说明解在左子树if(p.valroot.val&&q.val>root.val)returnlowestCommonAncestor(root.right,p,q)returnroot}解法二：非递归解法二是解法一的变体，思路相同，只是由递归改为非递归递归的。代码实现：varlowestCommonAncestor=function(root,p,q){while(root){if(p.valroot.val&&q.val>root.val){root=root.right}else{returnroot}}}在本文的结论中，我们回顾了以下树的概念，并通过实战概念进行了巩固.希望对你有所启发。最后，如果觉得内容有帮助，可以关注我的公众号《前端e进阶》，我整理了不同的学习专题。你也可以联系我加入我们的学习小组。参考资料https://time.geekbang.org/cou...
