注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex98 Validate Binary Search Tree  

2015-05-16 21:48:25|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
验证二叉搜索树

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.
这个还是要思考一下才能写出来的,必须开一个数组,递归的时候保存子树的最大值和最小值,也就是left是最小值,right必须是最大值,而且current的key必须大于左子树的最大值right,小于右子树的left最小值。这样想清楚了,递归代码就好写了。见c代码

/*
*平衡树的特性 : root->key 大于 left->key
root->key 小于 right->key
并且其子树也是平衡树
*/
int* traverse(struct TreeNode* current)
{

//需要构造一个数组,每次返回当树的 BST特性的判断 以及该树的最大元素和最小元素
if ((current->left == NULL) && (current->right == NULL))
{
int *result = (int*)malloc(3*sizeof(int));
result[0] = 1;
result[1] = current->val; //最小值 left
result[2] = current->val; //最大值 right
return result;
}
else
{
int *result = (int*)malloc(3 * sizeof(int));
int *leftResult=NULL,*rightResult=NULL;

if (current->left != NULL)
{
if (current->right != NULL)
{
leftResult = traverse(current->left);
rightResult = traverse(current->right);
if (rightResult[0] && leftResult[0]&&current->val>leftResult[2]&&current->val<rightResult[1])
{
result[0] = 1;
result[1] = leftResult[1]; //左子树的最小值
result[2] = rightResult[2];//右子树的最大值
}
else
{
result[0] = 0;
}
free(leftResult); //内存回收
leftResult = NULL;
free(rightResult);
rightResult = NULL;

}
else
{
leftResult = traverse(current->left);
if (leftResult[0] && current->val > leftResult[2])
{
result[0] = 1;
result[1] = leftResult[1]; //最小元素不变
result[2] = current->val; //最大元素更新为当前root的node值
}
else
{
result[0] = 0;
}
free(leftResult); //内存回收
leftResult = NULL;
}

}
else
{
rightResult = traverse(current->right);
if (rightResult[0] && current->val < rightResult[1])
{
result[0] = 1;
result[1] = current->val; //最小元素更新为当前root的node值
result[2] = rightResult[2]; //最大元素不变
}
else
{
result[0] = 0;
}
free(rightResult); //内存回收
rightResult = NULL;

}
return result;
}
}
bool isValidBST(struct TreeNode* root) {
if (root == NULL)
return true;
int *result = traverse(root);
bool mark = result[0];


free(result); //内存回收
result = NULL;
return mark;
}

update java version with neat code 2015/12/4

import ht.TreeNode;
public class ValidateBinarySearchTree {
public boolean isValidBST(TreeNode root) {
return helper(root);
}
private boolean helper(TreeNode root) {
if (root == null) {
return true;
}
if (root.left != null) {
TreeNode l = root.left;
while (l != null) {
if (l.val >= root.val) {
return false;
}
l = l.right;
}
}
if (root.right != null) {
TreeNode r = root.right;
while (r != null) {
if (r.val <= root.val) {
return false;
}
r = r.left;
}
}
return helper(root.left) && helper(root.right);
}
}



  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017