验证二叉搜索树

题目要求

你需要编写一个算法来判断给定的二叉树是否满足二叉搜索树的条件。二叉搜索树（BST）是一种特殊的二叉树，它满足以下性质：

1. 任意节点的左子树中的所有节点的值都小于该节点的值。
2. 任意节点的右子树中的所有节点的值都大于该节点的值。
3. 左子树和右子树也必须分别是二叉搜索树。

你的算法需要检查输入的二叉树根节点 root 是否符合上述所有条件。

解题思路

要判断一个二叉树是否是有效的二叉搜索树，我们可以采用以下几种思路：

1. 递归法：

   • 对于每个节点，检查其左子节点的值是否小于当前节点的值，右子节点的值是否大于当前节点的值。
   • 递归地对左子树和右子树进行相同的检查。
   • 注意，仅检查子节点的值是不够的，因为所有左子树中的节点都必须小于当前节点的值，所有右子树中的节点都必须大于当前节点的值。因此，我们需要维护当前值的有效最小值和最大值范围，并在递归过程中传递这些范围。

2. 中序遍历法：

   • 二叉搜索树的一个重要特性是，其中序遍历的结果是一个递增序列。
   • 我们可以对树进行中序遍历，并将节点的值存储在一个数组中。
   • 遍历完成后，检查数组是否是严格递增的。如果是，则树是一个有效的二叉搜索树；如果不是，树不是有效的二叉搜索树。
   • 为了优化空间复杂度，我们不必存储整个中序遍历序列，而是可以在遍历过程中实时检查序列是否递增。这可以通过保存前一个访问的节点的值，并与当前节点的值进行比较来实现。

3. 迭代法：

   • 使用栈来模拟中序遍历的过程。
   • 通过迭代而不是递归来遍历树，同时检查遍历的序列是否递增。

在实现上述任何一种方法时，都需要注意处理二叉树中可能存在的边界条件，例如树中的节点值可能包括整数的最大值和最小值。因此，初始化最大值和最小值时，不能简单地使用 int 或 long 的最大值和最小值，而应该使用更广泛的范围，或者使用特殊值来表示没有限制。

Golang 版本

package main

import (
	"fmt"
	"math"
)

// TreeNode defines a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// isValidBST is used to check if a tree is a valid binary search tree.
func isValidBST(root *TreeNode) bool {
	return validate(root, math.MinInt64, math.MaxInt64)
}

// validate is a helper function that uses the limits to check the validity of the tree.
func validate(node *TreeNode, lower, upper int) bool {
	if node == nil {
		return true
	}
	val := node.Val
	if val <= lower || val >= upper {
		return false
	}
	if !validate(node.Right, val, upper) {
		return false
	}
	if !validate(node.Left, lower, val) {
		return false
	}
	return true
}

func main() {
	// Example usage:
	// Construct a binary search tree:
	//       2
	//      / \
	//     1   3
	root := &TreeNode{Val: 2}
	root.Left = &TreeNode{Val: 1}
	root.Right = &TreeNode{Val: 3}

	// Check if it is a valid BST
	fmt.Println(isValidBST(root)) // Output: true
}

这段代码定义了一个TreeNode结构体，表示二叉树的节点，并实现了isValidBST函数来判断一个二叉树是否是有效的二叉搜索树。isValidBST函数通过调用validate辅助函数来递归地验证每个节点，同时传递当前节点值的有效范围。在main函数中，我们构建了一个简单的二叉搜索树示例，并调用isValidBST函数来验证它。

C++版本

#include <iostream>
#include <climits>

// 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 validate(root, LONG_MIN, LONG_MAX);
    }

private:
    bool validate(TreeNode* node, long long lower, long long upper) {
        if (node == nullptr) {
            return true;
        }

        int val = node->val;
        if (val <= lower || val >= upper) {
            return false;
        }

        if (!validate(node->right, val, upper)) {
            return false;
        }
        if (!validate(node->left, lower, val)) {
            return false;
        }

        return true;
    }
};

int main() {
    // Example usage:
    // Construct a binary search tree:
    //       2
    //      / \
    //     1   3
    TreeNode *root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);

    Solution solution;
    std::cout << std::boolalpha << solution.isValidBST(root) << std::endl; // Output: true

    // Clean up memory
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

这段 C++代码定义了一个TreeNode结构体，表示二叉树的节点，并实现了一个Solution类，其中包含了isValidBST方法来判断一个二叉树是否是有效的二叉搜索树。isValidBST方法通过调用私有的validate方法来递归地验证每个节点，同时传递当前节点值的有效范围。在main函数中，我们构建了一个简单的二叉搜索树示例，并调用isValidBST方法来验证它。最后，代码中还包括了适当的内存清理操作。

Python 版本

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def validate(node, low=float('-inf'), high=float('inf')):
            if not node:
                return True
            if not (low < node.val < high):
                return False
            return (validate(node.left, low, node.val) and
                    validate(node.right, node.val, high))

        return validate(root)

# Example usage:
if __name__ == "__main__":
    # Construct a binary search tree:
    #       2
    #      / \
    #     1   3
    root = TreeNode(2)
    root.left = TreeNode(1)
    root.right = TreeNode(3)

    # Check if it is a valid BST
    print(Solution().isValidBST(root))  # Output: True

这段 Python 代码定义了一个TreeNode类，表示二叉树的节点，并实现了一个Solution类，其中包含了isValidBST方法来判断一个二叉树是否是有效的二叉搜索树。isValidBST方法内部定义了一个嵌套的validate函数，用于递归地验证每个节点，同时传递当前节点值的有效范围。在__main__部分，我们构建了一个简单的二叉搜索树示例，并调用isValidBST方法来验证它。

Java 版本

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return validate(node.left, lower, node.val) && validate(node.right, node.val, upper);
    }
}

public class Main {
    public static void main(String[] args) {
        // Example usage:
        // Construct a binary search tree:
        //       2
        //      / \
        //     1   3
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        Solution solution = new Solution();
        System.out.println(solution.isValidBST(root)); // Output: true
    }
}

这段 Java 代码定义了一个TreeNode类，表示二叉树的节点，并实现了一个Solution类，其中包含了isValidBST方法来判断一个二叉树是否是有效的二叉搜索树。isValidBST方法通过调用私有的validate方法来递归地验证每个节点，同时传递当前节点值的有效范围。在Main类的main方法中，我们构建了一个简单的二叉搜索树示例，并调用isValidBST方法来验证它。

Rust 版本

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

use std::rc::Rc;
use std::cell::RefCell;
use std::i64;

struct Solution;

impl Solution {
    pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        Solution::validate(&root, i64::MIN, i64::MAX)
    }

    fn validate(node: &Option<Rc<RefCell<TreeNode>>>, lower: i64, upper: i64) -> bool {
        match node {
            Some(n) => {
                let n_borrowed = n.borrow();
                let val = n_borrowed.val as i64;
                if val <= lower || val >= upper {
                    return false;
                }
                Solution::validate(&n_borrowed.left, lower, val) &&
                Solution::validate(&n_borrowed.right, val, upper)
            },
            None => true,
        }
    }
}

fn main() {
    // Example usage:
    // Construct a binary search tree:
    //       2
    //      / \
    //     1   3
    let root = Some(Rc::new(RefCell::new(TreeNode::new(2))));
    let left = Some(Rc::new(RefCell::new(TreeNode::new(1))));
    let right = Some(Rc::new(RefCell::new(TreeNode::new(3))));

    if let Some(r) = root.as_ref() {
        r.borrow_mut().left = left;
        r.borrow_mut().right = right;
    }

    println!("{}", Solution::is_valid_bst(root)); // Output: true
}

这段 Rust 代码定义了一个TreeNode结构体，表示二叉树的节点，并实现了一个Solution结构体，其中包含了is_valid_bst方法来判断一个二叉树是否是有效的二叉搜索树。is_valid_bst方法通过调用私有的validate方法来递归地验证每个节点，同时传递当前节点值的有效范围。在main函数中，我们构建了一个简单的二叉搜索树示例，并调用is_valid_bst方法来验证它。

总结

无论是在 C++、Python、Java 还是 Rust 中，检查一个二叉树是否是二叉搜索树的基本算法思想是相同的。这个算法依赖于二叉搜索树的性质：对于树中的任意节点，其左子树中的所有节点的值都小于该节点的值，而其右子树中的所有节点的值都大于该节点的值。

为了实现这个算法，我们通常会使用递归函数，该函数会检查当前节点的值是否在允许的值范围内。这个范围是通过参数传递给递归调用的，初始调用时范围设置为整数类型能表示的最小值和最大值。对于每个节点，我们会更新这个范围：当我们向左子树递归时，我们将当前节点的值作为新的上界；当我们向右子树递归时，我们将当前节点的值作为新的下界。

如果在任何时候节点的值不在指定的范围内，或者左子树或右子树的递归调用返回false，那么整个函数返回false，表示这不是一个有效的二叉搜索树。如果递归检查通过所有节点都没有发现问题，那么函数返回true，表示这是一个有效的二叉搜索树。

在不同的编程语言中，这个算法的实现细节略有不同，主要是因为语言本身的语法和类型系统的差异。例如，Rust 使用Option<Rc<RefCell<TreeNode>>>来处理可能为空的节点和可变借用，而 C++使用nullptr来表示空指针，Python 和 Java 则有自己的方式来表示和处理空值。尽管如此，核心算法和逻辑结构在所有语言中都是一致的。