algorithm - 如何验证二叉搜索树？

Question

我在这里阅读了一个称为验证二叉搜索树的面试练习。

这究竟是如何工作的？在验证二叉搜索树时会寻找什么？我写了一个基本的搜索树，但从未听说过这个概念。

score 116 · Accepted Answer

事实上，这是每个人在面试时都会犯的错误。

Leftchild 必须检查 (minLimitof node,node.value)

Rightchild 必须检查 (node.value,MaxLimit of node)

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
         return true;
     if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

另一种解决方案（如果空间不是约束）：对树进行中序遍历并将节点值存储在数组中。如果数组按排序顺序，则它是有效的 BST，否则不是。

score 18 · Accepted Answer

“验证”二叉搜索树意味着您检查它是否确实在左侧有所有较小的项目，在右侧有大项目。本质上，它是检查二叉树是否是二叉搜索树。

score 16 · Accepted Answer

我找到的最佳解决方案是 O(n)，它不使用额外的空间。它类似于中序遍历，但不是将其存储到数组然后检查它是否已排序，我们可以使用静态变量并在中序遍历时检查数组是否已排序。

static struct node *prev = NULL;

bool isBST(struct node* root)
{
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;

        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
          return false;

        prev = root;

        return isBST(root->right);
    }

    return true;
}

score 7 · Accepted Answer

使用中序遍历的迭代解决方案。

bool is_bst(Node *root) {
  if (!root)
    return true;

  std::stack<Node*> stack;
  bool started = false;
  Node *node = root;
  int prev_val;

  while(true) {
    if (node) {
      stack.push(node);
      node = node->left();
      continue;
    }
    if (stack.empty())
      break;
    node = stack.top();
    stack.pop();

    /* beginning of bst check */
    if(!started) {
      prev_val = node->val();
      started = true;
    } else {
      if (prev_val > node->val())
        return false;
      prev_val = node->val();
    }
    /* end of bst check */

    node = node->right();
  }
  return true;
}

score 5 · Accepted Answer

这是我在 Clojure 中的解决方案：

(defstruct BST :val :left :right)

(defn in-order [bst]
  (when-let [{:keys [val, left, right]} bst]
    (lazy-seq
      (concat (in-order left) (list val) (in-order right)))))

(defn is-strictly-sorted? [col]
  (every?
    (fn [[a b]] (< a  b))
    (partition 2 1 col)))

(defn is-valid-BST [bst]
  (is-strictly-sorted? (in-order bst)))

score 3 · Accepted Answer

由于BST的中序遍历是一个非递减序列，我们可以利用这个性质来判断二叉树是否是BST。使用Morris 遍历和维护pre节点，我们可以得到O(n) 时间和 O(1) 空间复杂度的解。这是我的代码

public boolean isValidBST(TreeNode root) {
    TreeNode pre = null, cur = root, tmp;
    while(cur != null) {
        if(cur.left == null) {
            if(pre != null && pre.val >= cur.val) 
                return false;
            pre = cur;
            cur = cur.right;
        }
        else {
            tmp = cur.left;
            while(tmp.right != null && tmp.right != cur)
                tmp = tmp.right;
            if(tmp.right == null) { // left child has not been visited
                tmp.right = cur;
                cur = cur.left;
            }
            else { // left child has been visited already
                tmp.right = null;
                if(pre != null && pre.val >= cur.val) 
                    return false;
                pre = cur;
                cur = cur.right;
            }
        }
    }
    return true;
}

score 3 · Accepted Answer

这是我在 python 中的答案，它在hackerrank 网站上解决了所有的极端情况并经过了很好的测试

""" Node is defined as
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
"""

def checkBST(root):
    return checkLeftSubTree(root, root.left) and checkRightSubTree(root, root.right)

def checkLeftSubTree(root, subTree):
    if not subTree:
        return True
    else:
        return root.data > subTree.data \
        and checkLeftSubTree(root, subTree.left) \ 
        and checkLeftSubTree(root, subTree.right) \
        and checkLeftSubTree(subTree, subTree.left) \
        and checkRightSubTree(subTree, subTree.right)

def checkRightSubTree(root, subTree):
    if not subTree:
        return True
    else:
        return root.data < subTree.data \ 
        and checkRightSubTree(root, subTree.left) \
        and checkRightSubTree(root, subTree.right) \
        and checkRightSubTree(subTree, subTree.right) \
        and checkLeftSubTree(subTree, subTree.left)

score 1 · Accepted Answer

我最近在电话采访中得到了这个问题，并且比我应该做的更挣扎。我试图跟踪子节点中的最小值和最大值，但在面试的压力下，我无法将我的大脑包裹在不同的案例中。

昨晚睡着的时候想了想，意识到这就像在中序遍历期间跟踪您访问过的最后一个节点一样简单。在 Java 中：

public <T extends Comparable<T>> boolean isBst(TreeNode<T> root) {
    return isBst(root, null);
}

private <T extends Comparable<T>> boolean isBst(TreeNode<T> node, TreeNode<T> prev) {
    if (node == null)
        return true;

    if (isBst(node.left, prev) && (prev == null || prev.compareTo(node) < 0 ))
        return isBst(node.right, node);

    return false;
}

score 1 · Accepted Answer

bool BinarySearchTree::validate() {
    int minVal = -1;
    int maxVal = -1;
    return ValidateImpl(root, minVal, maxVal);
}

bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal)
{
    int leftMin = -1;
    int leftMax = -1;
    int rightMin = -1;
    int rightMax = -1;

    if (currRoot == NULL) return true;

    if (currRoot->left) {
        if (currRoot->left->value < currRoot->value) {
            if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false;
            if (leftMax != currRoot->left->value && currRoot->value < leftMax)  return false;
        }
        else
            return false;
    } else {
        leftMin = leftMax = currRoot->value;
    }

    if (currRoot->right) {
        if (currRoot->right->value > currRoot->value) {
            if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false;
            if (rightMin != currRoot->right->value && currRoot->value > rightMin)  return false;
        }
        else return false;
    } else {
        rightMin = rightMax = currRoot->value;
    }

    minVal = leftMin < rightMin ? leftMin : rightMin;
    maxVal = leftMax > rightMax ? leftMax : rightMax;

    return true;
}

score 1 · Accepted Answer

“最好先定义一个不变量。这里的不变量是——中序遍历中BST的任何两个顺序元素必须严格按照它们出现的顺序增加（不能相等，总是按顺序增加） “

score 1 · Accepted Answer

在 Java 中并允许在任一子树中具有相同值的节点：

public boolean isValid(Node node) {
    return isValid(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isValid(Node node, int minLimit, int maxLimit) {
    if (node == null)
        return true;
    return minLimit <= node.value && node.value <= maxLimit
            && isValid(node.left, minLimit, node.value)
            && isValid(node.right, node.value, maxLimit);
}

score 0 · Accepted Answer

要确定给定的 BT 是否是任何数据类型的 BST，您需要采用以下方法。1. 使用中序遍历调用递归函数直到叶节点结束 2. 自己构建最小值和最大值。

树元素必须具有小于/大于定义的运算符。

#define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal)
#define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal)

template <class T>
bool IsValidBST (treeNode &root)
{

   T min,  max;
   return IsValidBST (root, &min, &max);
}

template <class T>
bool IsValidBST (treeNode *root, T *MIN , T *MAX)
{
   T leftMin, leftMax, rightMin, rightMax;
   bool isValidBST;

   if (root->leftNode == NULL && root->rightNode == NULL)
   {
      *MIN = root->element;
      *MAX = root->element;
      return true;
   }

  isValidBST = IsValidBST (root->leftNode, &leftMin, &leftMax);

  if (isValidBST)
    isValidBST = IsValidBST (root->rightNode, &rightMin, &rightMax);

  if (isValidBST)
  {
     *MIN = MIN (leftMIN, rightMIN);
     *Max = MAX (rightMax, leftMax);
  }

  return isValidBST;
}

score 0 · Accepted Answer

我编写了一个使用 inorder Traversal BST 的解决方案，并检查节点是否按空间O(1)和时间递增顺序O(n)。TreeNode predecessor是上一个节点。我不确定解决方案是否正确。因为中序遍历不能定义一整棵树。

public boolean isValidBST(TreeNode root, TreeNode predecessor) {
    boolean left = true, right = true;
    if (root.left != null) {
        left = isValidBST(root.left, predecessor);
    }
    if (!left)
        return false;

    if (predecessor.val > root.val)
        return false;

    predecessor.val = root.val;
    if (root.right != null) {
        right = isValidBST(root.right, predecessor);
    }

    if (!right)
        return false;

    return true;

}

score 0 · Accepted Answer

递归很容易，但迭代方法更好，上面有一个迭代版本，但它过于复杂。这是您在任何地方都能找到的最佳解决方案：c++

该算法在O(N)时间上运行并且需要O(lgN)空间。

struct TreeNode
{
    int value;
    TreeNode* left;
    TreeNode* right;
};

bool isBST(TreeNode* root) {
    vector<TreeNode*> stack;
    TreeNode* prev = nullptr;
    while (root || stack.size()) {
        if (root) {
           stack.push_back(root);
           root = root->left;
        } else {
            if (prev && stack.back()->value <= prev->value)
                return false;
            prev = stack.back();
            root = prev->right;                    
            stack.pop_back();
        }
    }
    return true;
}

score 0 · Accepted Answer

以下是 BST 验证的 Java 实现，我们按顺序遍历树 DFS，如果我们得到任何大于最后一个数字的数字，它将返回 false。

static class BSTValidator {
  private boolean lastNumberInitialized = false;
  private int lastNumber = -1;

  boolean isValidBST(TreeNode node) {
    if (node.left != null && !isValidBST(node.left)) return false;

    // In-order visiting should never see number less than previous
    // in valid BST.
    if (lastNumberInitialized && (lastNumber > node.getData())) return false;
    if (!lastNumberInitialized) lastNumberInitialized = true;

    lastNumber = node.getData();

    if (node.right != null && !isValidBST(node.right)) return false;

    return true;
  }
}

score 0 · Accepted Answer

bool ValidateBST(Node *pCurrentNode, int nMin = INT_MIN, int nMax = INT_MAX)
{
    return
    (
        pCurrentNode == NULL
    )
    ||
    (
        (
            !pCurrentNode->pLeftNode ||
            (
                pCurrentNode->pLeftNode->value < pCurrentNode->value &&
                pCurrentNode->pLeftNode->value < nMax &&
                ValidateBST(pCurrentNode->pLeftNode, nMin, pCurrentNode->value)
            )
        )
        &&
        (
            !pCurrentNode->pRightNode ||
            (
                pCurrentNode->pRightNode->value > pCurrentNode->value &&
                pCurrentNode->pRightNode->value > nMin &&
                ValidateBST(pCurrentNode->pRightNode, pCurrentNode->value, nMax)
            )
        )
    );
}

score 0 · Accepted Answer

bool isBST(struct node* root)
{
    static struct node *prev = NULL;
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
            return false;
        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
            return false;
        prev = root;
        return isBST(root->right);
    }
    return true;
}

工作正常：）

score 0 · Accepted Answer

递归解决方案：

isBinary(root)
    {
        if root == null 
          return true
       else if( root.left == NULL and root.right == NULL)
          return true
       else if(root.left == NULL)
           if(root.right.element > root.element)
               rerturn isBInary(root.right)
        else if (root.left.element < root.element)
              return isBinary(root.left)
        else
              return isBInary(root.left) and isBinary(root.right)

    }

score 0 · Accepted Answer

迭代解决方案。

private static boolean checkBst(bst node) {

    Stack<bst> s = new Stack<bst>();
    bst temp;
    while(node!=null){
        s.push(node);
        node=node.left;
    }
    while (!s.isEmpty()){
        node = s.pop();
        System.out.println(node.val);
        temp = node;
        if(node.right!=null){
            node = node.right;
            while(node!=null)
            {
                //Checking if the current value is lesser than the previous value and ancestor.
                if(node.val < temp.val)
                    return false;
                if(!s.isEmpty())
                    if(node.val>s.peek().val)
                        return false;
                s.push(node);
                if(node!=null)
                node=node.left;
            }
        }
    }
    return true;
}

score 0 · Accepted Answer

// using inorder traverse based Impl
bool BinarySearchTree::validate() {
    int val = -1;
    return ValidateImpl(root, val);
}

// inorder traverse based Impl
bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) {
    if (currRoot == NULL) return true;

    if (currRoot->left) {
        if (currRoot->left->value > currRoot->value) return false;
        if(!ValidateImpl(currRoot->left, val)) return false;
    }

    if (val > currRoot->value) return false;
    val = currRoot->value;

    if (currRoot->right) {
        if (currRoot->right->value < currRoot->value) return false;
        if(!ValidateImpl(currRoot->right, val)) return false;
    }
    return true;
}

score 0 · Accepted Answer

这适用于重复项。

// time O(n), space O(logn)
// pseudocode
is-bst(node, min = int.min, max = int.max):
    if node == null:
        return true
    if node.value <= min || max < node.value:
        return false
    return is-bst(node.left, min, node.value)
        && is-bst(node.right, node.value, max)

这甚至适用于int.min和int.max使用Nullable类型的值。

// time O(n), space O(logn)
// pseudocode
is-bst(node, min = null, max = null):
    if node == null:
        return true
    if min != null && node.value <= min
        return false
    if max != null && max < node.value:
        return false
    return is-bst(node.left, min, node.value)
        && is-bst(node.right, node.value, max)

score 0 · Accepted Answer

一个班轮

bool is_bst(Node *root, int from, int to) {
   return (root == NULL) ? true :
     root->val >= from && root->val <= to &&
     is_bst(root->left, from, root->val) &&
     is_bst(root->right, root->val, to);
}

虽然很长的线。

score 0 · Accepted Answer

灵感来自http://www.jiuzhang.com/solutions/validate-binary-search-tree/

有两种通用的解决方案：遍历和分 && 征服。

public class validateBinarySearchTree {
    public boolean isValidBST(TreeNode root) {
        return isBSTTraversal(root) && isBSTDivideAndConquer(root);
    }

    // Solution 1: Traversal
    // The inorder sequence of a BST is a sorted ascending list
    private int lastValue = 0; // the init value of it doesn't matter.
    private boolean firstNode = true;
    public boolean isBSTTraversal(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!isValidBST(root.left)) {
            return false;
        }

        // firstNode is needed because of if firstNode is Integer.MIN_VALUE,
        // even if we set lastValue to Integer.MIN_VALUE, it will still return false
        if (!firstNode && lastValue >= root.val) {
            return false;
        }

        firstNode = false;
        lastValue = root.val;

        if (!isValidBST(root.right)) {
            return false;
        }

        return true;

    }

    // Solution 2: divide && conquer
    private class Result {
        int min;
        int max;
        boolean isBST;
        Result(int min, int max, boolean isBST) {
            this.min = min;
            this.max = max;
            this.isBST = isBST;
        }
    }

    public boolean isBSTDivideAndConquer(TreeNode root) {
        return isBSTHelper(root).isBST;
    }

    public Result isBSTHelper(TreeNode root) {
        // For leaf node's left or right
        if (root == null) {
            // we set min to Integer.MAX_VALUE and max to Integer.MIN_VALUE
            // because of in the previous level which is the leaf level,
            // we want to set the min or max to that leaf node's val (in the last return line)
            return new Result(Integer.MAX_VALUE, Integer.MIN_VALUE, true);
        }

        Result left = isBSTHelper(root.left);
        Result right = isBSTHelper(root.right);

        if (!left.isBST || !right.isBST) {
            return new Result(0,0, false);
        }

        // For non-leaf node
        if (root.left != null && left.max >= root.val
                && root.right != null && right.min <= root.val) {
            return new Result(0, 0, false);
        }

        return new Result(Math.min(left.min, root.val),
                Math.max(right.max, root.val), true);
    }
}

score 0 · Accepted Answer

该iterative函数迭代地检查给定的树是否是二叉搜索树。
该recurse函数递归地检查给定的树是否是二叉搜索树。
在iterative函数中，我使用 bfs 来检查 BST。
在recurse函数中，我使用 dfs 来检查 BST。
两种解决方案的时间复杂度均为O(n)
iterative解决方案比解决方案具有优势recurse，即iterative解决方案可以提前停止。
甚至recurse可以通过全局标志值优化功能以提前停止。
两种解决方案的想法是左孩子应该在 -infinity 的范围内，其父节点的值是根节点
右子节点应该在 +infinity 的范围内，其父节点的值是根节点

并继续比较当前节点在范围内的值。如果任何节点的值不在范围内，则返回 False

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.iterative(root)
        # return self.recurse(root, float("inf"), float("-inf"))

    def iterative(self, root):
        if not root:
            return True

        level = [[root, -float("inf"), float("inf")]]

        while level:
            next_level = []

            for element in level:
                node, min_val, max_val = element
                if min_val<node.val<max_val:
                    if node.left:
                        next_level.append([node.left, min_val, node.val])
                    if node.right:
                        next_level.append([node.right, node.val, max_val])
                else:
                    return False
            level = next_level

        return True

    def recurse(self, root, maxi, mini):
        if root is None:
            return True

        if root.val < mini or root.val > maxi:
            return False

        return self.recurse(root.left, root.val-1, mini) and self.recurse(root.right, maxi, root.val+1)

score 0 · Accepted Answer

Python 实现示例。此示例使用类型注释。然而，由于 Node 类使用自身，我们需要包含作为模块的第一行：

from __future__ import annotations

否则，你会得到name 'Node' is not defined错误。这个例子也以dataclass为例。为了检查它是否是 BST，它使用递归来检查左右节点的值。

"""Checks if Binary Search Tree (BST) is balanced"""

from __future__ import annotations
import sys
from dataclasses import dataclass

MAX_KEY = sys.maxsize
MIN_KEY = -sys.maxsize - 1


@dataclass
class Node:
    value: int
    left: Node
    right: Node

    @property
    def is_leaf(self) -> bool:
        """Check if node is a leaf"""
        return not self.left and not self.right


def is_bst(node: Node, min_value: int, max_value: int) -> bool:
    if node.value < min_value or max_value < node.value:
        return False
    elif node.is_leaf:
        return True

    return is_bst(node.left, min_value, node.value) and is_bst(
        node.right, node.value, max_value
    )


if __name__ == "__main__":
    node5 = Node(5, None, None)
    node25 = Node(25, None, None)
    node40 = Node(40, None, None)
    node10 = Node(10, None, None)

    # balanced tree
    node30 = Node(30, node25, node40)
    root = Node(20, node10, node30)
    print(is_bst(root, MIN_KEY, MAX_KEY))

    # unbalanced tree
    node30 = Node(30, node5, node40)
    root = Node(20, node10, node30)
    print(is_bst(root, MIN_KEY, MAX_KEY))

score 0 · Accepted Answer

这是来自 sedgewick 算法类的 java 解决方案。在此处查看完整的 BST 实施

我添加了一些解释性评论

private boolean isBST() {
    return isBST(root, null, null);

}

private boolean isBST(Node x, Key min, Key max) {
    if (x == null) return true;
    // when checking right subtree min is key of x's parent
    if (min != null && x.key.compareTo(min) <= 0) return false;
    // when checking left subtree, max is key of x's parent
    if (max != null && x.key.compareTo(max) >= 0) return false;
    // check left subtree and right subtree
    return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);

}

score 0 · Accepted Answer

使用 inOrder 遍历..

首先使用中序遍历将树值添加到数组中。

然后遍历数组，添加一个标志值 true 以拆分根元素之后和根元素之前的元素。

添加计数器以检查树是否具有具有相同根值的元素。

最小值和最大值设置为范围

var isValidBST = function(root) 
{

    
    if(!root) return false;
    
 
    let current = root;
    let data = [];
    let flag = false;
    let counter = 0;
    
    function check(node){
        if(node.left){
            check(node.left);
        }
        data.push(node.val);
        if(node.right){
            check(node.right);
        }
       
    }
    
    
    let min = Number.MIN_SAFE_INTEGER;
    let max = root.val;
    for(let i = 0; i < data.length; i++){
        
        if(data[i] == root.val){
            flag = true;
            counter++;
        }
        
        if(flag){
            if(data[i] < root.val || data[i] < max || counter > 1){
                return false;
            }
            else{
                
                max = data[i];
            }
            
            
        }
        else{
            if(data[i] > root.val || data[i] <= min|| counter > 1){
                return false
            }
            else {
                min = data[i]
            }
        }
    }
    
    return true;
    

};

score 0 · Accepted Answer

BST 示例

    public bool IsBinarySearchTree(TreeNode root)
    {
        return IsValid(root, long.MinValue, long.MaxValue);
    }

    private static bool IsValid(TreeNode node, long min, long max)
    {
        if (node == null)
        {
            return true;
        }

        if (node.Value >= max || node.Value <= min)
        {
            return false;
        }

        return IsValid(node.Left, min, node.Value) && IsValid(node.Right, node.Value, max);
    }

在哪里TreeNode

   public class TreeNode
   {
       public int Value;
       public TreeNode Left;
       public TreeNode Right;

       public TreeNode(int value)
       {
           Value = value;
       }
   }

这是详细说明https://codestandard.net/articles/validate-binary-search-tree/

score 0 · Accepted Answer

We have to recursively ask each node if its left branch and right branch are valid binary search trees. The only thing each time we ask, we have to pass correct left and right boundaries:

class Solution:
    def is_bst(self,root:TreeNode):
        if not root:
            return True
        # left and right are boundaries
        def dfs(node,left,right):
            if not node:
                return True
            if not (node.val>left and node.val<right):
                return False
            # when we move right, we update the left, when we move left we update the right
            return dfs(node.left,left,node.val) and dfs(node.right,node.val,right)
        return dfs(root, float("-inf"), float("+inf"))

score -1 · Accepted Answer

这是不使用额外空间的迭代解决方案。

Node{
     int value;
     Node right, left
  }

  public boolean ValidateBST(Node root){
    Node currNode = root;
    Node prevNode = null;
    Stack<Node> stack = new Stack<Node>();
    while(true){
        if(currNode != null){
            stack.push(currNode);
            currNode = currNode.left;
            continue;
        }
        if(stack.empty()){
            return;
        }
        currNode = stack.pop();
        if(prevNode != null){
            if(currNode.value < prevNode.value){
                return false;
            }
        }
        prevNode = currNode;
        currNode = currNode.right;
    }
}

score -1 · Accepted Answer

 private void validateBinarySearchTree(Node node) {
    if (node == null) return;

    Node left = node.getLeft();
    if (left != null) {
        if (left.getData() < node.getData()) {
            validateBinarySearchTree(left);
        } else {
            throw new IllegalStateException("Not a valid Binary Search tree");
        }
    }

    Node right = node.getRight();
    if (right != null) {
        if (right.getData() > node.getData()) {
            validateBinarySearchTree(right);
        } else {
            throw new IllegalStateException("Not a valid Binary Search tree");
        }
    }
}

score -3 · Accepted Answer

boolean isBST(Node root) {
    if (root == null) { return true; }
    return (isBST(root.left) && (isBST(root.right) && (root.left == null || root.left.data <= root.data) && (root.right == null || root.right.data > root.data));
}

score -3 · Accepted Answer

这是我用 JavaScript 编写的递归解决方案

function isBST(tree) {
  if (tree === null) return true;

  if (tree.left != undefined && tree.left.value > tree.value) {
    return false;
  }

  if (tree.right != undefined && tree.right.value <= tree.value) {
    return false;
  }

  return isBST(tree.left) && isBST(tree.right);
}

algorithm - 如何验证二叉搜索树？

33 回答 33

Related

Reference