【面试】判断一棵二叉树是否为二叉排序树

Java基础

浏览数:164

2019-3-19

AD:资源代下载服务

一、描述

  给定一棵二叉树,如何判断一棵树是否是二叉排序树。给出树结点定义如下

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;
    }
}

 

PS:如果您觉得阅读本文对您有帮助,请点一下“推荐”按钮,您的“推荐”,将会是我不竭的动力!

作者:leesf    掌控之中,才会成功;掌控之外,注定失败。

出处:http://www.cnblogs.com/leesf456/

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。


如果觉得本文对您有帮助,您可以请我喝杯咖啡!