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.

Analyze

一开始的想法是用后续遍历判断子节点是否为二分搜索树, 实现如下:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  return isValidBSTChild(root)
};

var isValidBSTChild = function(node) {
  if (!node || (!node.left && !node.right)) return true

  const isLeftChildValidBST = isValidBSTChild(node.left)
  const isRightChildValidBST = isValidBSTChild(node.right)
  if (!isLeftChildValidBST || !isRightChildValidBST) return false

  // defination for BST tree
  if (node.right && node.left && node.right.val > node.val && node.val > node.left.val) return true
  if (node.right && !node.left && node.right.val > node.val) return true
  if (node.left && !node.right && node.left.val < node.val) return true
  return false
};

结果卡在了如下测试用例中:

10
   /  \
  5   15
     /  \
    6   20

Input: [10,5,15,null,null,6,20]
Expect Output: false

参考评论区的点拨, 题目等价为经过中序遍历输出后的节点是否为升序排列。再次实现:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  const analyze = []
  inOrderTraverse(root, analyze)
  for (let i = 0; i < analyze.length; i++) {
    if (analyze[i] >= analyze[i + 1]) return false
  }
  return true
};

var inOrderTraverse = function(node, analyzeArr) {
  if (!node) return
  inOrderTraverse(node.left, analyzeArr)
  analyzeArr.push(node.val)
  inOrderTraverse(node.right, analyzeArr)
}