[leet code] Validate Binary Search Tree

发布时间:2014-10-22 18:22:34编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"[leet code] Validate Binary Search Tree",主要涉及到[leet code] Validate Binary Search Tree方面的内容,对于[leet code] 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. =============== Analysis: Basic idea is to validate all rules of BST for each node in the given binary tree.  Accordingly, for each node (current node), we compare it to all the nodes in its left sub-tree, and all the node in its right sub-tree.  If there is any node in in its left or right sub-trees vibrates the BST rule, return false.  Otherwise, further check current node's left child and right child. Obviously, we need a recursive function to check all the nodes in given binary tree.  Besides, for compare current node with all the nodes in its left and right sub-trees, we need another recursive function. One more thing need to be careful is to define the false condition while comparing current node to nodes in its left and right sub-trees. /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isValidBST(TreeNode root) { if(root == null) return true; // exit // compare current node with all nodes in its left sub-tree and right sub-tree (be careful!) if(!helper(root.val, root.left, true)||!helper(root.val, root.right, false)) return false; // current node validated return isValidBST(root.left) && isValidBST(root.right); } public boolean helper(int value, TreeNode node, boolean left){ if(node == null) return true; if(left == true && node.val >= value) return false; if(left == false && node.val <= value) return false; return helper(value, node.left, left) && helper(value, node.right, left); } }


上一篇:UIWebview与Js交互
下一篇:lucene lock 机制

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款