编程知识 cdmana.com

Verification of binary search tree (Java implementation)

Title Description

Given a binary tree , Determine whether it is an effective binary search tree .

Suppose a binary search tree has the following characteristics :

  • The left subtree of a node contains only the number of nodes smaller than the current node .
  • The right subtree of a node contains only the number of nodes greater than the current node .
  • All left and right subtrees themselves must also be binary search trees .

Example  1:

Input :
    2
    / \
  1   3
Output : true

Example  2:

Input :
    5
    / \
  1   4
      / \
    3   6
Output : false
explain : Input is : [5,1,4,null,null,3,6].
          The value of the root node is 5 , But the value of its right child node is 4 .

source : Power button (LeetCode) link :https://leetcode-cn.com/problems/validate-binary-search-tree

Their thinking

To solve this problem, we should first understand what properties of binary search tree can be used by us , From the information given by the title, we can know : If the left subtree of the binary tree is not empty , Then the values of all nodes on the left subtree are less than the values of its root nodes ; If its right subtree is not empty , Then the value of all nodes on the right subtree is greater than the value of its root node ; Its left and right subtrees are also binary search trees .

This inspires us to design a recursive function helper(root, lower, upper) To judge recursively , Function means to consider with root Root subtree , Determine whether the values of all nodes in the subtree are in (l,r)(l,r) Within the scope of ( Notice the open range ). If root The value of the node val be not in (l,r)(l,r) If the condition is not satisfied, return directly , Otherwise, we need to continue to call recursively to check whether the left and right subtrees satisfy , If they are satisfied, it means that this is a binary search tree .

So according to the properties of the binary search tree , When the left subtree is called recursively , We need to put the upper bound upper Change it to root.val, That is to call helper(root.left, lower, root.val), Because the value of all nodes in the left subtree is less than the value of its root node . Similarly, when the right subtree is called recursively , We need to put the lower bound lower Change it to root.val, That is to call helper(root.right, root.val, upper).

Reference link :https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/

Solution code

Complexity analysis

Time complexity : O(n), among n Is the number of nodes in a binary tree . In recursive calls, each node of the binary tree is accessed at most once , So the time complexity is zero O(n).

Spatial complexity : O(n), among n Is the number of nodes in a binary tree . Recursive functions in the recursive process need to allocate stack space for each layer of recursive functions , So extra space is needed here, and that space depends on the depth of the recursion , The height of the binary tree . In the worst case, a binary tree is a chain , The height of the tree is n , The deepest recursion reaches n layer , So in the worst case, the space complexity is O(n) .

/**
 * 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);
    }

    public boolean helper(TreeNode node, Integer lower, Integer upper) {
        if (node == null) {
            return true;
        }

        int val = node.val;
        if (lower != null && val <= lower) {
            return false;
        }
        if (upper != null && val >= upper) {
            return false;
        }

        if (!helper(node.right, val, upper)) {
            return false;
        }
        if (!helper(node.left, lower, val)) {
            return false;
        }
        return true;
    }
}

 

版权声明
本文为[Cheng Yu]所创,转载请带上原文链接,感谢

Scroll to Top