给你一个二叉树的根节点 root
,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3] 输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
- 树中节点数目范围在
[1, 104]
内 -231 <= Node.val <= 231 - 1
方法一:递归
时间复杂度:O(n)
空间复杂度:O(n)
1 /** 2 * Defination for a binary tree node. 3 * function TreeNode(val,left,right){ 4 * this.val=(val===undefined?0:val) 5 * this.left=(left===undefined?null:left) 6 * this.right=(right===undefined?null:right) 7 * } 8 */ 9 /** 10 * @param {TreeNode} root 11 * @param {boolean} 12 */ 13 const helper = (root, lower, upper) => { 14 if (root === null) { 15 return true; 16 } 17 if (root.val <= lower || root.val >= upper) { 18 return false; 19 } 20 return ( 21 helper(root.left, lower, root.val) && helper(root.right, root.val, upper) 22 ); 23 }; 24 var isValidBST = function(root) { 25 return helper(root, -Infinity, Infinity); 26 };
方法二:中序遍历
时间复杂度:O(n)
空间复杂度:O(n)
1 /** 2 * Defination for a binary tree node 3 * function TreeNode(val,left,right){ 4 * this.val=(val===undefined?0:val) 5 * this.left=(left===undefined?null:left) 6 * this.right=(right===undefined?null:right) 7 * } 8 */ 9 /** 10 * @param {TreeNode} root 11 * @return {boolean} 12 */ 13 14 var isValidBST = function(root) { 15 let stack = []; 16 let inorder = -Infinity; 17 while (stack.length || root !== null) { 18 while (root !== null) { 19 stack.push(root); 20 root = root.left; 21 } 22 root = stack.pop(); 23 //如果中序遍历得到的节点值小于等于前一个inorder,说明不是二叉搜索树 24 if (root.val <= inorder) { 25 return false; 26 } 27 inorder = root.val; 28 root = root.val; 29 } 30 return true; 31 };
原文地址:http://www.cnblogs.com/icyyyy/p/16854251.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性