LeetCode - Medium - 98. Validate Binary Search Tree-蒲公英云

LeetCode - Medium - 98. Validate Binary Search Tree

迷南。 2022-10-06 10:52 134阅读 0赞

Topic

Tree
Recursion
Depth-first Search

Description

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

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.

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

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

Constraints:

The number of nodes in the tree is in the range [ 1 , 1 0 4 ] [1, 10^4] [1,104].
− 2 31 < = N o d e . v a l < = 231 − 1 -2^{31} <= Node.val <= 2{31} - 1 −231<=Node.val<=231−1

Analysis

方法一：我写的，中序遍历模式递归版。

方法二：我写的，中序遍历模式迭代版。

方法三：别人写的，前序遍历模式递归版。

Submission

import java.util.LinkedList;
import com.lun.util.BinaryTree.TreeNode;
public class ValidateBinarySearchTree { 
    //方法一：我写的，中序遍历模式递归版
    public boolean isValidBST(TreeNode root) { 
        Integer[] prev = { null};
        boolean[] result = { true};
        isValidBST(root, prev, result);
        return result[0];
    }
    private void isValidBST(TreeNode node, Integer[] prev, boolean[] result) { 
        if(node == null || !result[0]) return;
        isValidBST(node.left, prev, result);
        if(prev[0] != null && prev[0] >= node.val) { 
            result[0] = false;
            return;
        }
        prev[0] = node.val;
        isValidBST(node.right, prev, result);
    }
    //方法二：我写的，中序遍历模式迭代版
    public boolean isValidBST2(TreeNode root) { 
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        Integer prev = null;
        while(!stack.isEmpty() || p != null) { 
            if(p != null) { 
                stack.push(p);
                p = p.left;
            }else { 
                TreeNode node = stack.pop();
                if(prev != null && prev >= node.val)
                    return false;
                prev = node.val;
                p = node.right;
            }
        }
        return true;
    }
    //方法三：别人写的，前序遍历模式递归版
    public boolean isValidBST3(TreeNode root) { 
        return isValidBST3(root, null, null);
    }
    private boolean isValidBST3(TreeNode root, Integer min, Integer max) { 
        if(root == null) return true;
        if(min != null && root.val <= min) return false;
        if(max != null && root.val >= max) return false;
        return isValidBST3(root.left, min, root.val) && isValidBST3(root.right, root.val, max);
    }
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.BinaryTree;
public class ValidateBinarySearchTreeTest { 
    @Test
    public void test() { 
        ValidateBinarySearchTree obj = new ValidateBinarySearchTree();
        assertTrue(obj.isValidBST(BinaryTree.integers2BinaryTree(2,1,3)));
        assertFalse(obj.isValidBST(BinaryTree.integers2BinaryTree(5,1,4,null,null,3,6)));
        assertFalse(obj.isValidBST(BinaryTree.integers2BinaryTree(5,4,6,null,null,3,7)));
    }
    @Test
    public void test2() { 
        ValidateBinarySearchTree obj = new ValidateBinarySearchTree();
        assertTrue(obj.isValidBST2(BinaryTree.integers2BinaryTree(2,1,3)));
        assertFalse(obj.isValidBST2(BinaryTree.integers2BinaryTree(5,1,4,null,null,3,6)));
        assertFalse(obj.isValidBST2(BinaryTree.integers2BinaryTree(5,4,6,null,null,3,7)));
    }
    @Test
    public void test3() { 
        ValidateBinarySearchTree obj = new ValidateBinarySearchTree();
        assertTrue(obj.isValidBST2(BinaryTree.integers2BinaryTree(2,1,3)));
        assertFalse(obj.isValidBST2(BinaryTree.integers2BinaryTree(5,1,4,null,null,3,6)));
        assertFalse(obj.isValidBST2(BinaryTree.integers2BinaryTree(5,4,6,null,null,3,7)));
    }
}