98. Validate Binary Search Tree

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

Question

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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.

初想法

这题的第一想法就是用dfs去做，因为这题在遍历的过程中，和父节点的关系非常明显：

• 父节点是所有左子节点的最大值
• 父节点是所有右子节点的最小值

这题过程中最浪费我时间的是： 如何保证子节点和父节点之间值的正确比较？

多画图的话，思路会明显清晰一些：

pub fn vertical_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    if root.is_none() {
        return true;
    }
    fn dfs(
        node: Option<Rc<RefCell<TreeNode>>>,
        min_val: i32,
        max_val: i32,
        valid: bool,
        is_root: bool,
        is_min: bool,
        is_max: bool,
    ) -> bool {
        if valid == false {
            return valid;
        }
        if let Some(unwrapped_node) = node {
            let left = unwrapped_node.borrow_mut().left.take();
            let right = unwrapped_node.borrow_mut().right.take();
            let value = unwrapped_node.borrow().val;
            if !is_root && (!is_min && value <= min_val || !is_max && value >= max_val)
                || !dfs(left, min_val, value, valid, false, is_min, false)
                || !dfs(right, value, max_val, valid, false, false, is_max)
            {
                return false;
            }
        }
        return true;
    }
    return dfs(root, i32::MIN, i32::MAX, true, true, true, true);
}

总结

BST题目中有不同的特性，要合理的选择遍历方法，基础的其实就只有dfs和bfs，抓住这两者之间的特点就好了。

同时注意和父子节点的关系，和极值时候的情况。