首页 > 代码库 > 【面试】判断一棵二叉树是否为二叉排序树
【面试】判断一棵二叉树是否为二叉排序树
一、描述
给定一棵二叉树，如何判断一棵树是否是二叉排序树。给出树结点定义如下
class TreeNode { int key; TreeNode left; TreeNode right; public TreeNode(int key) { this.key = key; }}
二、解题思路
根据二叉排序树的性质，在进行中序遍历的时候，当前结点的值总是大于前驱结点的值，需要在遍历时保存前驱结点的值，这样有利于进行判断，基于这样的思路来进行解题。
三、代码
根据以上的解题思路（遍历时利用二叉排序树的性质），即可得到如下的代码。
/** * Created by LEESF on 2016/9/8. */class TreeNode { int key; TreeNode left; TreeNode right; public TreeNode(int key) { this.key = key; }}public class IsBSTree { static boolean flag = true; static int last = Integer.MIN_VALUE; public static boolean isBSTree(TreeNode root) { if (root.left != null && flag) isBSTree(root.left); if (root.key < last) flag = false; last = root.key; if (root.right != null && flag) isBSTree(root.right); return flag; }}
【面试】判断一棵二叉树是否为二叉排序树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。