设为首页 加入收藏

TOP

[互联网面试笔试汇总C/C++-14] 判断一棵二叉树是否是二叉搜索树-微策略
2014-11-23 21:45:51 】 浏览:5313
Tags:互联网 面试 笔试 汇总 C/C -14 判断 是否是 搜索 策略
首先看一下二叉搜索树的定义:
或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
原理:一棵二叉搜索树的中续遍历结果是从小到大排序好的,反之亦然。
代码:时间复杂度O(n),空间复杂度O(1)
bool isBSTInOrder(BinaryTree *root)   
{  
  int prev = INT_MIN;  
  return isBSTInOrderHelper(root, prev);  
}  
/*该函数判断二叉树p是否是一棵二叉搜索树,且其结点值都大于prev*/  
bool isBSTInOrderHelper(BinaryTree *p, int& prev)   
{  
  if (!p) return true;  
  if (isBSTInOrderHelper(p->left, prev)) { // 如果左子树是二叉搜索树,且结点值都大于prev  
    if (p->data > prev) { //判断当前结点值是否大于prev,因为此时prev已经设置为已经中序遍历过的结点的最大值。  
      prev = p->data;  
      return isBSTInOrderHelper(p->right, prev); //若结点值大于prev,则设置prev为当前结点值,并判断右子树是否二叉搜索树且结点值都大于prev。  
    } else {  
      return false;  
    }  
  }  
  else {  
    return false;  
  }  
}  

如果觉得上面的思路不好理解,可以先对二叉搜索树进行中序遍历,然后将遍历结果存放到一个数组中,然后判断这个数组是否是从小到大排好序,而且无重复元素的。时间复杂度O(n),空间复杂度O(n).
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇[互联网面试笔试汇总C/C++-13] 写.. 下一篇[互联网面试笔试汇总C/C++-16] 判..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目