数据结构与算法之 leetcode 98. 验证二叉搜索树 (前序，中序，后序遍历)

98. 验证二叉搜索树

前序遍历

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {boolean}*/var isValidBST = function(root,left = Number.MIN_SAFE_INTEGER,right = Number.MAX_SAFE_INTEGER){if(root==null){return true}const x = root.val;return left<x&&x<right&&isValidBST(root.left,left,x)&&isValidBST(root.right,x,right)
}

执行用时分布
72ms
击败24.56%
使用 JavaScript 的用户消耗内存分布
53.21MB
击败84.13%
使用 JavaScript 的用户

中序遍历

// 中序遍历
var isValidBST = function (root) {let pre = Number.MIN_SAFE_INTEGER;function dfs(node){if (node == null) {return true;}if (!dfs(node.left)||(node.val <= pre)){return false;}pre = node.val;return dfs(node.right);}return dfs(root)
};

执行用时分布
72ms
击败24.56%
使用 JavaScript 的用户消耗内存分布
53.34MB
击败56.75%
使用 JavaScript 的用户

后序遍历

// 后序遍历var isValidBST = function (root) {function dfs(node){if(node == null){return [Number.MAX_SAFE_INTEGER,Number.MIN_SAFE_INTEGER]}const [lMin,lMax] = dfs(node.left)const [rMin,rMax] = dfs(node.right)const x = node.valif(x<=lMax||x>=rMin){return [Number.MIN_SAFE_INTEGER,Number.MAX_SAFE_INTEGER]}return [Math.min(lMin,x),Math.max(rMax,x)]}return dfs(root)[1]!=Number.MAX_SAFE_INTEGER
}

执行用时分布
75ms
击败13.61%
使用 JavaScript 的用户
消耗内存分布
57.01MB
击败5.01%
使用 JavaScript 的用户

参考链接

98. 验证二叉搜索树