二叉搜索树中查找比指定值大的最小值;二叉搜索树中查找比指定值小的最大值

小鱼儿 2022-02-13 09:08 241阅读 0赞

> 题目要求：  
> 1、二叉搜索树中查找比指定值大的最小值;  
> 2、二叉搜索树中查找比指定值小的最大值  
> 说明：本文二叉搜索树中不包含重复值

@Data
        class Node{ 
            private Node left;
            private Node right;
            private int data;
    
            public Node(int data){ 
               this.data=data;
            }
        }
    
        /** * 二叉搜索树中（没有重复值时） 查找比target大的最小值 * @param node * @param target */
    
        public Integer find1(Node node, int target){ 
            if(node == null)return null;
            if(node.data <= target){ 
            //这里目的是从根节点向下找，直到找到第一个比target大的节点。
               return find1(node.right, target);
            } else { 
            //找到第一个比target大的节点（记为node0）后，比target大的最小值肯定在node0的左子树内。
            //所以查找左子树，返回值为空说明左子树没有结果，则去当前节点值
                Integer x= find1(node.left, target);
                return (x == null) ? node.data : x;
            }
        }
    
        /** * 二叉搜索树中（没有重复值时） 查找比target小的最大值 * @param node * @param target */
    
        public Integer find2(Node node, int target){ 
            if(node == null)return null;
            if(node.data >= target){ 
                return find2(node.left, target);
            } else { 
                Integer x= find2(node.right, target);
                return (x == null) ? node.data : x;
            }
        }
    
        @Test
        public void findtest(){ 
            Node node10 = new Node(10);//root
            Node node5 = new Node(5);
            node10.left=node5;
            Node node18 = new Node(18);
            node10.right=node18;
            Node node1 = new Node(1);
            Node node6 = new Node(6);
            Node node17 = new Node(17);
            Node node19 = new Node(19);
            Node node7 = new Node(7);
            Node node16 = new Node(16);
            node5.left=node1;
            node5.right=node6;
            node6.right=node7;
            node18.left=node17;
            node18.right=node19;
            node17.left=node16;
    
            int target = 18;
            System.out.println("比 " + target + "大的最小值是：" + find1(node10, target));
            System.out.println("比 " + target + "小的最大值是：" + find2(node10, target));
        }