[LeetCode] 98. 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.

Example 1:

    2
   / 
  1   3

Input: [2,1,3]
Output: true

Example 2:

    5
   / 
  1   4
     / 
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

验证二叉搜索树。

题目即是题意。二叉搜索树的特性是对于每个node而言，他的左子树上任意节点都比他自身小，右子树上任意节点都比他自身大。这个题也是有两种做法，迭代和递归。时间空间复杂度都是O(n)。

迭代

迭代的做法会利用到inorder的做法，也是用到一个栈。按照inorder的顺序遍历所有的node，记录一个pre node和一个currrent node。因为是inorder的关系，如果这个BST是有效的，inorder的遍历结果会是有序的。

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {boolean}
 4  */
 5 var isValidBST = function (root) {
 6     if (root === null) return true;
 7     let stack = [];
 8     let cur = root;
 9     let pre = null;
10     while (cur !== null || stack.length) {
11         while (cur !== null) {
12             stack.push(cur);
13             cur = cur.left;
14         }
15         cur = stack.pop();
16         if (pre !== null && cur.val <= pre.val) {
17             return false;
18         }
19         pre = cur;
20         cur = cur.right;
21     }
22     return true;
23 };

Java实现

 1 class Solution {
 2     public boolean isValidBST(TreeNode root) {
 3         // corner case
 4         if (root == null) {
 5             return true;
 6         }
 7 
 8         // normal case
 9         Stack<TreeNode> stack = new Stack<>();
10         TreeNode cur = root;
11         TreeNode pre = null;
12         while (cur != null || !stack.isEmpty()) {
13             while (cur != null) {
14                 stack.push(cur);
15                 cur = cur.left;
16             }
17             cur = stack.pop();
18             if (pre != null && cur.val <= pre.val) {
19                 return false;
20             }
21             pre = cur;
22             cur = cur.right;
23         }
24         return true;
25     }
26 }

递归

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {boolean}
 4  */
 5 var isValidBST = function (root) {
 6     if (root === null) return true;
 7     return helper(root, null, null);
 8 };
 9 
10 var helper = function (root, min, max) {
11     if (root === null) return true;
12     if (min !== null && root.val <= min) return false;
13     if (max !== null && root.val >= max) return false;
14     return helper(root.left, min, root.val) && helper(root.right, root.val, max);
15 }

[更新] 另一种递归

利用inorder递归，再判断数组是否有序。

时间O(n)

空间O(n) - 递归的栈空间O(n) + 存放节点的数组O(n)

 1 /**
 2  * @param {TreeNode} root
 3  * @return {boolean}
 4  */
 5 var isValidBST = function (root) {
 6     let res = [];
 7     if (root === null) return true;
 8     inorder(res, root);
 9     for (let i = 1; i < res.length; i++) {
10         if (res[i] <= res[i - 1]) return false;
11     }
12     return true;
13 };
14 
15 var inorder = function (res, root) {
16     if (root === null) return true;
17     inorder(res, root.left);
18     res.push(root.val);
19     inorder(res, root.right);
20 }

Java实现

 1 class Solution {
 2     public boolean isValidBST(TreeNode root) {
 3         if (root == null) return true;
 4         return helper(root, null, null);
 5     }
 6 
 7     private boolean helper(TreeNode root, Integer min, Integer max) {
 8         if (root == null) return true;
 9         if (min != null && root.val <= min) return false;
10         if (max != null && root.val >= max) return false;
11         return helper(root.left, min, root.val) && helper(root.right, root.val, max);
12     }
13 }

LeetCode 题目总结