/  

daily leetcode - validate-binary-search-tree - !

题目地址

https://leetcode.com/problems/validate-binary-search-tree/

题目描述

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.

Example 1:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

思路

这道验证二叉搜索树有很多种解法，可以利用它本身的性质来做，即左<根<右，也可以通过利用中序遍历结果为有序数列来做，下面我们先来看最简单的一种，就是利用其本身性质来做，初始化时带入系统最大值和最小值，在递归过程中换成它们自己的节点值，用long代替int就是为了包括int的边界条件，代码如下：

C++ 解法一：

// Recursion without inorder traversal
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }
    bool isValidBST(TreeNode* root, long mn, long mx) {
        if (!root) return true;
        if (root->val <= mn || root->val >= mx) return false;
        return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx);
    }
};

Java 解法一：

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean valid(TreeNode root, long low, long high) {
        if (root == null) return true;
        if (root.val <= low || root.val >= high) return false;
        return valid(root.left, low, root.val) && valid(root.right, root.val, high);
    }
}

这题实际上简化了难度，因为有的时候题目中的二叉搜索树会定义为左<=根<右，而这道题设定为一般情况左<根<右，那么就可以用中序遍历来做。因为如果不去掉左=根这个条件的话，那么下边两个数用中序遍历无法区分：

20 20
/
20 20

它们的中序遍历结果都一样，但是左边的是 BST，右边的不是 BST。去掉等号的条件则相当于去掉了这种限制条件。下面来看使用中序遍历来做，这种方法思路很直接，通过中序遍历将所有的节点值存到一个数组里，然后再来判断这个数组是不是有序的，代码如下：

C++ 解法二：

// Recursion
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        vector<int> vals;
        inorder(root, vals);
        for (int i = 0; i < vals.size() - 1; ++i) {
            if (vals[i] >= vals[i + 1]) return false;
        }
        return true;
    }
    void inorder(TreeNode* root, vector<int>& vals) {
        if (!root) return;
        inorder(root->left, vals);
        vals.push_back(root->val);
        inorder(root->right, vals);
    }
};

Java 解法二：

public class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        for (int i = 0; i < list.size() - 1; ++i) {
            if (list.get(i) >= list.get(i + 1)) return false;
        }
        return true;
    }
    public void inorder(TreeNode node, List<Integer> list) {
        if (node == null) return;
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }
}

下面这种解法跟上面那个很类似，都是用递归的中序遍历，但不同之处是不将遍历结果存入一个数组遍历完成再比较，而是每当遍历到一个新节点时和其上一个节点比较，如果不大于上一个节点那么则返回 false，全部遍历完成后返回 true。代码如下：

C++ 解法三：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode *pre = NULL;
        return inorder(root, pre);
    }
    bool inorder(TreeNode* node, TreeNode*& pre) {
        if (!node) return true;
        bool res = inorder(node->left, pre);
        if (!res) return false;
        if (pre) {
            if (node->val <= pre->val) return false;
        }
        pre = node;
        return inorder(node->right, pre);
    }
};

当然这道题也可以用非递归来做，需要用到栈，因为中序遍历可以非递归来实现，所以只要在其上面稍加改动便可，代码如下：

C++ 解法四：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode *p = root, *pre = NULL;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            if (pre && p->val <= pre->val) return false;
            pre = p;
            p = p->right;
        }
        return true;
    }
};

Java 解法四：

public class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode p = root, pre = null;
        while (p != null || !s.empty()) {
            while (p != null) {
                s.push(p);
                p = p.left;
            }
            p = s.pop();
            if (pre != null && p.val <= pre.val) return false;
            pre = p;
            p = p.right;
        }
        return true;
    }
}

最后还有一种方法，由于中序遍历还有非递归且无栈的实现方法，称之为 Morris 遍历，可以参考博主之前的博客 Binary Tree Inorder Traversal，这种实现方法虽然写起来比递归版本要复杂的多，但是好处在于是 O(1) 空间复杂度，参见代码如下：

C++ 解法五:

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if (!root) return true;
        TreeNode *cur = root, *pre, *parent = NULL;
        bool res = true;
        while (cur) {
            if (!cur->left) {
                if (parent && parent->val >= cur->val) res = false;
                parent = cur;
                cur = cur->right;
            } else {
                pre = cur->left;
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = NULL;
                    if (parent->val >= cur->val) res = false;
                    parent = cur;
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};

思路2

中序遍历

这道题是让你验证一棵树是否为二叉查找树（BST）。 由于中序遍历的性质如果一个树遍历的结果是有序数组，那么他也是一个二叉查找树(BST),
我们只需要中序遍历，然后两两判断是否有逆序的元素对即可，如果有，则不是BST，否则即为一个BST。

定义法

根据定义，一个结点若是在根的左子树上，那它应该小于根结点的值而大于左子树最大值；若是在根的右子树上，那它应该大于根结点的值而小于右子树最小值。也就是说，每一个结点必须落在某个取值范围：

  1. 根结点的取值范围为（考虑某个结点为最大或最小整数的情况）：(long_min, long_max)
  2. 左子树的取值范围为：(current_min, root.value)
  3. 右子树的取值范围为：(root.value, current_max)

关键点解析

  • 二叉树的基本操作（遍历）
  • 中序遍历一个二叉查找树（BST）的结果是一个有序数组
  • 如果一个树遍历的结果是有序数组，那么他也是一个二叉查找树(BST)

代码

中序遍历

  • 语言支持：JS，C++, Java

JavaScript Code：

/*
 * @lc app=leetcode id=98 lang=javascript
 *
 * [98] Validate Binary Search Tree
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    if (root === null) return true;
    if (root.left === null && root.right === null) return true;
    const stack = [root];
    let cur = root;
    let pre = null;

    function insertAllLefts(cur) {
        while(cur && cur.left) {
            const l = cur.left;
            stack.push(l);
            cur = l;
        }
    }
    insertAllLefts(cur);

    while(cur = stack.pop()) {
        if (pre && cur.val <= pre.val) return false;
        const r = cur.right;

        if (r) {
            stack.push(r);
            insertAllLefts(r);
        }
        pre = cur;
    }

    return true;
};

C++ Code：

// 递归
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return validateBstInorder(root, prev);
    }
    
private:
    bool validateBstInorder(TreeNode* root, TreeNode*& prev) {
        if (root == nullptr) return true;
        if (!validateBstInorder(root->left, prev)) return false;
        if (prev != nullptr && prev->val >= root->val) return false;
        prev = root;
        return validateBstInorder(root->right, prev);
    }
};

// 迭代
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        auto s = vector<TreeNode*>();
        TreeNode* prev = nullptr;
        while (root != nullptr || !s.empty()) {
            while (root != nullptr) {
                s.push_back(root);
                root = root->left;
            }
            root = s.back();
            s.pop_back();
            if (prev != nullptr && prev->val >= root->val) return false;
            prev = root;
            root = root->right;
        }
        return true;
    }
};

Java Implementation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<Integer> stack = new Stack<> ();
        TreeNode previous = null;

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (previous != null && root.val <= previous.val ) return false;
            previous = root;
            root = root.right;
        }
        return true;
    }
}

定义法

  • 语言支持：C++，Python3, Java

C++ Code：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// 递归
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
private:
    bool helper(const TreeNode* root, long min, long max) {
        if (root == nullptr) return true;
        if (root->val >= max || root->val <= min) return false;
        return helper(root->left, min, root->val) && helper(root->right, root->val, max);
    }
};

// 循环
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        auto ranges = queue<pair<long, long>>();
        ranges.push(make_pair(LONG_MIN, LONG_MAX));
        auto nodes = queue<const TreeNode*>();
        nodes.push(root);
        while (!nodes.empty()) {
            auto sz = nodes.size();
            for (auto i = 0; i < sz; ++i) {
                auto range = ranges.front();
                ranges.pop();
                auto n = nodes.front();
                nodes.pop();
                if (n->val >= range.second || n->val <= range.first) {
                    return false;
                }
                if (n->left != nullptr) {
                    ranges.push(make_pair(range.first, n->val));
                    nodes.push(n->left);
                }
                if (n->right != nullptr) {
                    ranges.push(make_pair(n->val, range.second));
                    nodes.push(n->right);
                }
            }
        }
        return true;
    }
};

Python Code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode, area: tuple=(-float('inf'), float('inf'))) -> bool:
        """思路如上面的分析，用Python表达会非常直白
        :param root TreeNode 节点
        :param area tuple 取值区间
        """
        if root is None:
            return True
        
        is_valid_left = root.left is None or\
                   (root.left.val < root.val and area[0] < root.left.val < area[1])
        is_valid_right = root.right is None or\
                   (root.right.val > root.val and area[0] < root.right.val < area[1])
        
        # 左右节点都符合，说明本节点符合要求
        is_valid = is_valid_left and is_valid_right
        
        # 递归下去
        return is_valid\
            and self.isValidBST(root.left, (area[0], root.val))\
            and self.isValidBST(root.right, (root.val, area[1]))

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    private boolean helper(TreeNode root, Integer lower, Integer higher) {
        if (root == null) return true;

        if (lower != null && root.val <= lower) return false;
        if (higher != null && root.val >= higher) return false;

        if (!helper(root.left, lower, root.val)) return false;
        if (!helper(root.right, root.val, higher)) return false;

        return true;
    }
}

本文参考自：
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode

标题: daily leetcode - validate-binary-search-tree - !
文章作者: lonuslan
文章链接: https://louislan.com/articles/2020/04/19/1587263566100.html
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hi I'm LouisLan！
    评论
    0 评论
avatar
文章
189
标签
20
分类
4
管理登录
主页
时间轴
标签
分类
友情链接
关于我
我的开源
我的笔记
chatgpt
取消