首页 > 其他 > 详细

LintCode Validate Binary Search Tree

时间:2016-08-11 06:22:13      阅读:115      评论:0      收藏:0      [点我收藏+]

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 thanthe node‘s key.
  • Both the left and right subtrees must also be binary search trees.
  • A single node tree is a BST

Example

An example:

  2
 / 1   4
   /   3   5
 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int val) {
 7  *         this.val = val;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     /**
14      * @param root: The root of binary tree.
15      * @return: True if the binary tree is BST, or false
16      */
17     public boolean isValidBST(TreeNode root) {
18         // write your code here
19         if (root == null) {
20             return true;
21         }
22         if ((root.left == null) && (root.right == null)) {
23             return true;
24         }
25         
26         boolean left = false;
27         boolean right = false;
28         if (root.left == null) {
29             left = true;
30         }
31         else if ((root.left != null) && (root.left.val < root.val)) {
32             left = isValidBST(root.left);
33         }else {
34             return false;
35         }
36         
37         if (root.right == null) {
38             right = true;
39         }
40         else if ((root.right != null) && (root.right.val > root.val)) {
41             right = isValidBST(root.right);
42         }else {
43             return false;
44         }
45         
46         return left && right;
47     }
48 }

 

LintCode Validate Binary Search Tree

原文:http://www.cnblogs.com/ly91417/p/5759495.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!