本文转载自微信公众号《程序员熊》，作者饭饭。转载本文请联系程序员小熊公众号。前言大家好，我是华为程序员小熊。今天给大家带来一道二叉树相关的面试高频题。这道题半年内被谷歌、字节跳动、微软、亚马逊等大公司用作面试题。树。本文主要介绍递归和深度优先搜索两种方法来解答这个问题，供大家参考，希望对大家有所帮助。验证二叉搜索树给你一个二叉树的根节点来判断它是否是一个有效的二叉搜索树。有效的二叉搜索树定义如下：节点的左子树仅包含小于当前节点的数字。节点的右子树仅包含大于当前节点的数字。所有的左子树和右子树本身必须是二叉搜索树。例1例2和提示二叉搜索树题目已经提示有效的二叉搜索树的定义如下：一个节点的左子树只包含小于当前节点的数。节点的右子树仅包含大于当前节点的数字。所有的左子树和右子树本身必须是二叉搜索树。例子例子1例子1例子2例子3二叉查找树的判断对于上面的例子，根据二叉查找树的判断方法，判断上面的例子是否为二叉查找树，如下：例子1不是二叉查找树.原因：根节点（值为6）的左子树的节点数（值为7）大于根节点数。示例2不是二叉搜索树。原因：根节点（值为6）的右子树的节点数（值为3）小于根节点数。示例3不是二叉搜索树。原因：根节点的左子树不是二叉查找树，左子树的根节点的值5不仅小于左子节点的值7而且大于右子节点的值4子节点，根节点的值6小于左子树的值，中间节点的值为7；根节点的右子树不是二叉搜索树，右子树根节点的值8不仅大于右子节点的值3，而且小于左子节点的值9，并且根节点6的值大于右子树中节点的值3。解题思路根据二叉搜索树的定义，判断一棵树是否为二叉搜索树，需要判断每个节点是否符合二叉树的性质，判断的依据是一样的，所以可以用递归的方法来回答这个问题。上述递归判断的依据（假设当前节点有左子节点和右子节点）是指：当前节点的值大于其左子节点的值；当前节点的值小于其右子节点的值；如果当前节点有左右子节点树，则左右子树上的节点也必须满足：左子树上节点的值小于当前节点的值，且左子树上节点的值右子树大于当前节点的值；根据以上思路，可以设置上下界，判断节点是否符合二叉搜索树的性质。如果存在上下界，则判断该节点是否在上下界之内，如果不在，则不是二叉搜索树；否则，以该节点的值作为上界，递归判断其左子树，以该节点的值作为下界，递归判断其右子树。请注意，空树是二叉搜索树。给我看看CodeCboolisValidBST_Helper(structTreeNode*root,doublemin,doublemax){/*特殊判断*/if(root==NULL){returntrue;}/*当前节点不在上下界，不是二叉搜索树*/if(root->val<=min||root->val>=max){returnfalse;}/*判断左右子树是否为二叉查找树*/returnisValidBST_Helper(root->left,min,root->val)&&isValidBST_Helper(root->right,root->val,max);}boolisValidBST(structTreeNode*root){returnisValidBST_Helper(root,LONG_MIN,LONG_MAX);}C++boolisValidBST_Helper(TreeNode*root,doublemin,doublemax){if(root==nullptr){returntrue;}if(root->val<=min||root->val>=max){returnfalse;}returnisValidBST_Helper(root->left,min,root->val)&&isValidBST_Helper(root->right,root->val,max);}boolisValidBST(TreeNode*root){returnisValidBST_Helper(root,LONG_MIN,LONG_MAX);}JavabooleanisValidBST_Helper(TreeNoderoot,doublemin,doublemax){if(root==null){returntrue;}if(root.val<=min||root.val>=max){returnfalse;}returnisValidBST_Helper(root.左，最小，root.val)&&isValidBST_Helper(root.right,root.val,max);}booleanisValidBST(TreeNoderoot){returnisValidBST_Helper(root,Long.MIN_VALUE,Long.MAX_VALUE);}Python3defisValidBST(self,root:TreeNode)->bool:defisValidBST_Helper(root),min,right):ifrootisNone:returnTrueifroot.val<=minorroot.val>=right:returnFalsereturnisValidBST_Helper(root.left,min,root.val)andisValidBST_Helper(root.right,root.val,right)returnisValidBST_Helper(root,-float('inf'),float('inf'))GolangfuncisValidBST(root*TreeNode)bool{returnisValidBST_Helper(root,math.MinInt64,math.MaxInt64)}funcisValidBST_Helper(root*TreeNode,min,maxint)bool{ifroot==nil{returntrue}ifmin>=root.Val||max<=root.Val{returnfalse}returnisValidBST_Helper(root.Left,min,root.Val)&&isValidBST_Helper(root.Right,root.Val,max)}复杂度分析时间复杂度度数：O(n)，其中n为二叉树节点数空间复杂度：O(n)。深度优先搜索是根据二叉搜索树的性质，按顺序遍历，得到的数组必须是升序排列。因此，根据这个特性，可以判断一棵树是否是二叉搜索树。如果采用中序遍历，将二叉树所有节点的值存储在一个数组中，然后判断数组是否升序就有点繁琐了。由于判断数组是否升序，只需要判断数组的最后一个元素是否大于前一个元素，所以这道题可以设置一个变量保存中序遍历中前一个节点的值，然后判断当前节点的值是否大于变量持有的值。如果不大于，说明这棵树不是二叉搜索树；否则继续遍历判断。告诉我CodeC++longpre=LONG_MIN;boolisValidBST(TreeNode*root){if(root==nullptr){returntrue;}if(!isValidBST(root->left)){returnfalse;}if(root->val<=pre){returnfalse;}pre=root->val;returnisValidBST(root->right);}Javalongtemp=Long.MIN_VALUE;booleanisValidBST(TreeNoderoot){if(root==null){returntrue;}if(!isValidBST(root.left)){returnfalse;}if(root.val<=temp){returnfalse;}temp=root.val;returnisValidBST(root.right);}复杂度分析时间复杂度：O(n)，其中n为二叉树节点数。空间复杂度：O(n)。
