leetcode validate binary search tree

题目:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees

这道题我想了个解法,就是为每一棵树设置上下界,用递归的算法求解。

然而报错,因为在设置上下限的时候,用Integer.max_value表示正无穷,Integer.min_value表示负无穷,

然而在具体操作的时候,树中有可能就存在Integer.max_value或者Integer.min_value
从而产生错误。

百度了一下,有个很巧妙的解法

即,对BST进行中序遍历,中序遍历的结果必然是升序的。

这道题的解法告诉我们,BST的中序遍历结果是个升序的数组

原文地址:https://www.cnblogs.com/elnino/p/5541495.html