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)
}