将排序链表转换成二叉搜索树

川长思鸟来 2022-05-19 07:45 170阅读 0赞

![这里写图片描述][70]

//链表的节点
     class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; next = null; }
      }
    
    //树的节点
     class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }
    
    public class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            if(head==null) return null;
    
             return ListToBST(head,null);
        }
        //递归调用获得二叉搜索树
        public TreeNode ListToBST(ListNode head,ListNode tail){
              if(head==tail) return null;
              //申请两个指针，快慢指针
              ListNode fast=head;
              ListNode slow=head;
              while(fast!=tail&&fast.next!=tail){
                  fast=fast.next.next;
                  slow=slow.next;
              }
              TreeNode root=new TreeNode(slow.val);//根节点的定义
              root.left=ListToBST(head,slow);       //递归调用
              root.right=ListToBST(slow.next,tail);
    
              return root;
        }
    
        //二叉搜索树的遍历
        public void InorderTree(TreeNode root){
    
           if(root!=null){
               InorderTree(root.left);
               System.out.println(root.val);
               InorderTree(root.right);
           }
        }
    
        public static void main(String[]args){
           //System.out.println("Hello World!");
           ListNode head=new ListNode(1);
           head.next=new ListNode(2);
           head.next.next=new ListNode(3);
           head.next.next.next=new ListNode(4);
    
           Solution s=new Solution();
           TreeNode root=s.sortedListToBST(head);
           s.InorderTree(root);
    
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220519/2d22f6f9d2f840e49f7763383ef41abf.png
[70 1]: /images/20220519/d50f17d55c62444f8207bc10aa53638f.png