current position:Home>Algorithm exercise 19: search Binary Tree

Algorithm exercise 19: search Binary Tree

2022-01-27 02:39:54 Wow, click, click

 Give you the root node of a binary tree  root , Determine whether it is an effective binary search tree .
 It works   The binary search tree is defined as follows :
 The left subtree of the node contains only   Less than   Number of current nodes .
 The right subtree of the node contains only   Greater than   Number of current nodes .
 All left and right subtrees themselves must also be binary search trees .

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.

 Algorithm exercises 19: Search binary trees _ Binary search tree

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

     
  • 1.
  • 2.

 Algorithm exercises 19: Search binary trees _ minimum value _02

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

     
  • 1.
  • 2.
  • 3.
package com.example.springboot;


import java.util.*;
public class Test2 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
      // Search binary trees 
      public boolean isValidBST(TreeNode root) {
          return   isSearch(root).isBST;
      }
      public Info isSearch(TreeNode root){
        // If the binary tree is empty , return null
          if(root==null){
              return  null;
          }
          Info searchLeft = isSearch(root.left);
          Info searchRight = isSearch(root.right);
          // Set the maximum and minimum values to be the current values 
          int max=root.val;
          int min= root.val;
          // If the left node is not empty , Find the maximum and minimum values of the left node 
          if(searchLeft!=null){
              max=Math.max(max, searchLeft.max);
              min=Math.min(min,searchRight.min);
          }
          // If the right node is not empty , Find the maximum and minimum values of the right node 
          if(searchRight!=null){
              max=Math.max(max,searchRight.max);
              min=Math.min(min,searchRight.min);
          }
          // If the maximum value of the left node is less than the current value , And the minimum value on the right is greater than the current node , Then the search tree conditions are met 
         boolean isBST=true;
        if(searchLeft!=null && !searchLeft.isBST){
            isBST=false;
        }
        if(searchRight!=null && !searchRight.isBST){
            isBST=false;
        }
        return new Info(isBST,max,min);
      }
      public class Info{
       public boolean isBST;
       public int max;
       public int min;
        public Info(boolean isBST,int max,int min){
            this.isBST=isBST;
            this.max=max;
            this.min=min;
        }
      }

}

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.

copyright notice
author[Wow, click, click],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270239522791.html

Random recommended