跳至主要內容

98, 验证二叉搜索树

Mike大约 4 分钟binary treemediumbinary treedepth first searchbinary search tree

一、题目描述

给你一个二叉树的根节点root,判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1

输入: root = [2, 1, 3]
输出: true

示例 2

输入: root = [5, 1, 4, null, null, 3, 6]
输出: false
解释: 根节点的值是5,但是右子节点的值是4

提示

  • 树中节点数目范围在[1, 10⁴]
  • -2³¹ <= Node.val <= 2³¹ - 1

相关主题

  • 深度优先搜索
  • 二叉搜索树
  • 二叉树

二、题解

#[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,
        }
    }
}

方法 1: 夹逼定理

pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    //Self::dfs_recur_1(root)
    //Self::dfs_iter_1(root)
    Self::bfs_iter_1(root)
}

///
/// 深度优先搜索, 递归
///
fn dfs_recur_1(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    const DETERMINE: fn(Option<Rc<RefCell<TreeNode>>>, i64, i64) -> bool =
        |root, min, max| match root {
            None => true,
            Some(curr) => {
                let curr_val = curr.borrow().val as i64;
                if !(min < curr_val && curr_val < max) {
                    return false;
                }

                let left = curr.borrow_mut().left.take();
                let right = curr.borrow_mut().right.take();

                DETERMINE(left, min, curr_val) && DETERMINE(right, curr_val, max)
            }
        };

    DETERMINE(root, i64::MIN, i64::MAX)
}

///
/// 深度优先搜索, 迭代
///
fn dfs_iter_1(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    if let Some(root) = root {
        let mut stack = vec![(root, i64::MIN, i64::MAX)];

        while let Some((curr, min, max)) = stack.pop() {
            let curr_val = curr.borrow().val as i64;
            if !(min < curr_val && curr_val < max) {
                return false;
            }

            if let Some(right) = curr.borrow_mut().right.take() {
                stack.push((right, curr_val, max));
            }
            if let Some(left) = curr.borrow_mut().left.take() {
                stack.push((left, min, curr_val));
            }
        }
    }

    true
}

///
/// 广度优先搜索, 迭代
///
fn bfs_iter_1(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    if let Some(root) = root {
        let mut queue = VecDeque::from([(root, i64::MIN, i64::MAX)]);

        while let Some((curr, min, max)) = queue.pop_front() {
            let curr_val = curr.borrow().val as i64;
            if !(min < curr_val && curr_val < max) {
                return false;
            }

            if let Some(left) = curr.borrow_mut().left.take() {
                queue.push_back((left, min, curr_val));
            }
            if let Some(right) = curr.borrow_mut().right.take() {
                queue.push_back((right, curr_val, max));
            }
        }
    }

    true
}

方法 2: 中序遍历是有序的

pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    //Self::dfs_recur_2(root)
    Self::dfs_iter_2(root)
}

///
/// 深度优先搜索, 递归
///
fn dfs_recur_2(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    let mut vals = vec![];
    const DETERMINE: fn(Option<Rc<RefCell<TreeNode>>>, &mut Vec<i32>) -> bool =
        |root, vals| match root {
            None => true,
            Some(curr) => {
                if !DETERMINE(curr.borrow_mut().left.take(), vals) {
                    return false;
                }

                let curr_val = curr.borrow().val;
                if !vals.last().map_or(true, |&prev_val| curr_val > prev_val) {
                    return false;
                }
                vals.push(curr_val);

                DETERMINE(curr.borrow_mut().right.take(), vals)
            }
        };

    DETERMINE(root, &mut vals)
}

///
/// 深度优先搜索, 迭代
///
fn dfs_iter_2(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    if let Some(root) = root {
        let mut vals = vec![];
        let mut stack = vec![Ok(root)];

        while let Some(curr) = stack.pop() {
            match curr {
                Ok(node) => {
                    if let Some(right) = node.borrow_mut().right.take() {
                        stack.push(Ok(right));
                    }

                    stack.push(Err(node.borrow().val));

                    if let Some(left) = node.borrow_mut().left.take() {
                        stack.push(Ok(left));
                    }
                }
                Err(curr_val) => {
                    if !vals.last().map_or(true, |&prev_val| curr_val > prev_val) {
                        return false;
                    }

                    vals.push(curr_val);
                }
            }
        }
    }

    true
}