二叉搜索树的相关算法

1.在二叉搜索树中，查找任意两个节点的最近公共父节点

public <T extends Comparable<T>> TreeNode<T>  getFather(TreeNode<T> root,TreeNode<T> p,TreeNode<T> q){
        if(root==null|| p.equals(root)|| q.equals(root)){
            return root;
        }
        
        if(root.value.compareTo(p.value)>0 && root.value.compareTo(q.value)>0){
            TreeNode<T> left=getFather(root.left,p,q);
            return left;
        }
        if(root.value.compareTo(p.value)<0 && root.value.compareTo(q.value)<0){
            TreeNode<T> right=getFather(root.right,p,q);
            return right;
        }
        
        return root;
        
    }

2.在二叉查找树中寻找两个节点，使它们的和为一个给定值

image.png

public boolean findTarget(TreeNode<Integer> root,Integer target){
        List<TreeNode> list=new ArrayList<>();
        inOrder(root,list);
        int left=0;
        int right=list.size()-1;
        

        while(left<right){
            TreeNode<Integer> node1=list.get(left);
            TreeNode<Integer> node2=list.get(right);
            if(node1.value+node2.value==target){
                return true;
            }
            else if(node1.value+node2.value>target){
                right=right-1;
            }
            else{
                left=left+1;
            }
        }
        return false;
        
        
    }
    
    public void inOrder(TreeNode<Integer> root,List list){
        if(root==null){
            return;
        }
        inOrder(root.left,list);
        list.add(root);
        inOrder(root.right,list);
        
    }

3.Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

image.png

辅助类

public class Holder {
    boolean flag=false;

}

    private T value;
    int count=0;//count为啥不能作为参数传进去
/*
     * 
     */
    /*
     * 寻找二叉查找树的第 k 个元素
     */
    public T getK(TreeNode<T> root,int k){
        
        ///boolean flag=false;
        Holder holder=new Holder();
        inOrderTraversal(root,k,holder);
        return value;
    }
    
    public void inOrderTraversal(TreeNode<T> root,int k,Holder holder){
        
    
        if(holder.flag==true){
            return;
        }
        if(root== null){
            return;
        }
        inOrderTraversal(root.left,k,holder);
        
        count++;
        if(count==k){
            value= root.value;
            holder.flag=true;
            //return;
        }
        //System.out.println(count+"."+root.value+holder.flag);

        inOrderTraversal(root.right,  k,holder);
        
        
    }

4.二叉搜索树中一个节点的前驱(找二叉树中一个节点的前驱，算法和这个一样)

        TreeNode<T> pre;
    private T preValue;
    private int preCnt;
    public T getPreElement(TreeNode root,TreeNode p){
        inOrderTraversalPre(root,p);
        return preValue;
    }
    
    public void inOrderTraversalPre(TreeNode<T> root,TreeNode node){
        if(root== null){
            return;
        }
        inOrderTraversalPre(root.left,node);
        
        preCnt++;
        if(preCnt==1){
            preValue=null;
            pre=root;

        }
        
        //System.out.println(preCnt+"."+root.value);
        else{
            if(!root.value.equals(node.value)){
                pre=root;
            }
            
            if(root.value.equals(node.value)){
                preValue=pre.value;
            }
        }
        
        
        inOrderTraversalPre(root.right,  node);
        
        
    }

5.二叉搜索树中一个节点的后继(找二叉树中一个节点的后继，算法和这个一样)

int postCnt=0;
private int temp;
private T postValue;

/**
     * 
     * @param root
     * @param p
     * @return
     *<p>Description: 查找指定元素的后继</p>
     */
    public T getPostElement(TreeNode root,TreeNode p){
        Holder holder=new Holder();
        inOrderTraversal(root,p,holder);
        return postValue;
    }
    public void inOrderTraversal(TreeNode<T> root,TreeNode node,Holder holder){
        if(holder.flag==true){
            return;
        }
        if(root== null){
            return;
        }
        inOrderTraversal(root.left,node,holder);
        
        postCnt++;
        
        //System.out.println(postCnt+"."+root.value+holder.flag);
        if(root.value.equals(node.value)){

            temp=postCnt;
        }
        
        if(postCnt==temp+1){
            postValue=root.value;
            holder.flag=true;
        }
        
        inOrderTraversal(root.right,  node,holder);
        
        
    }

6.从有序链表中构造二叉搜索树
快慢指针找链表的中间位置

    /**
     * 
     * @param head
     * @return
     *<p>Description:找有序链表的中间位置的前驱 </p>
     */
    public MyNode getPreOfMid(MyNode head){
        MyNode fast=head;
        MyNode slow=head;
        MyNode pre=head;
        while(fast!=null && fast.getNext()!=null){
            pre=slow;
            slow=slow.getNext();
            fast=fast.getNext().getNext();
        }
        //System.out.println(slow.getData());
        return pre;
        
    }

构造二叉搜索树

 public TreeNode sortedListToBST(MyNode head) {
            if(head==null){
                return null;
            }
            if(head.getNext()==null){
                return new TreeNode(head.getData());
            }
            MyNode pre=getPreOfMid(head);
            MyNode mid=pre.getNext();
            pre.setNext(null);//断开链表
            TreeNode root=new TreeNode(mid.getData());
            root.left=sortedListToBST(head);
            root.right=sortedListToBST(mid.getNext());
            return root;
        }