首页 > 其他 > 详细

验证二叉查找树

时间:2015-08-05 22:13:25      阅读:207      评论:0      收藏:0      [点我收藏+]

二叉查找树

给定一个二叉树,判断它是否是合法的二叉查找树(BST)

一棵BST定义为:

节点的左子树中的值要严格小于该节点的值。
节点的右子树中的值要严格大于该节点的值。
左右子树也必须是二叉查找树。

因为二叉查找树的中序遍历是有序的。所以验证是否为二叉查找树,用中序遍历这个二叉树,如果前一个结点的值大于当前结点的值,则证明这个不是二叉树。

代码实现

bool isValidBST(TreeNode *root) {
        // write your code here
        if(root == NULL)
            return true;
        stack<TreeNode*> stk;
        TreeNode *pre = NULL;

        while(root || !stk.empty())
        {
            if(root)
            {
                stk.push(root);
                root = root->left;
            }

            else
            {
                root = stk.top();
                stk.pop();
                if(pre && (root->val <= pre->val))
                    return false;
                pre = root;
                root = root->right;
            }
        }

        return true;
    }

(95) Validate Binary Search Tree
http://www.lintcode.com/zh-cn/problem/validate-binary-search-tree/

版权声明:本文为博主原创文章,未经博主允许不得转载。

验证二叉查找树

原文:http://blog.csdn.net/zwhlxl/article/details/47304399

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