109. 有序链表转换二叉搜索树

系统管理员 2023-02-20 12:16 4阅读 0赞

# 题目来源 #

[109. 有序链表转换二叉搜索树][109.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]  
类似的题目：[108. 将有序数组转换为二叉搜索树][108.]

# 题目解析 #

## 递归 ##

跟[108. 将有序数组转换为二叉搜索树][108.]不同的是，数组取中很容易使用下标得到，但是链表没那么容易，不过我们可以使用快慢指针来取得终点。当获取到链表的中点作为而二叉树节点的时候，我们还需要得到该节点的左右子树  
由于我们得到的是一个有序链表而不是数组，我们不能直接使用下标来访问元素。我们需要知道链表中的中间元素。  
我们可以利用两个指针来访问链表中的中间元素。假设我们有两个指针 slow\_ptr 和 fast\_ptr。slow\_ptr 每次向后移动一个节点而 fast\_ptr 每次移动两个节点。当 fast\_ptr 到链表的末尾时 slow\_ptr 就访问到链表的中间元素。对于一个偶数长度的数组，中间两个元素都可用来作二叉搜索树的根。  
当找到链表中的中间元素后，我们将链表从中间元素的左侧断开，做法是使用一个 prev\_ptr 的指针记录 slow\_ptr 之前的元素，也就是满足 prev\_ptr.next = slow\_ptr。断开左侧部分就是让 prev\_ptr.next = None。  
我们只需要将链表的头指针传递给转换函数，进行高度平衡二叉搜索树的转换。所以递归调用的时候，左半部分我们传递原始的头指针；右半部分传递 slow\_ptr.next 作为头指针。

**一个很容易出错的点：当链表中只有一个节点的时候就要及时返回，因为它是无法通过快慢指针取中的，只会进入死循环**

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode sortedListToBST(ListNode head) {
        
              if (head == null){
        
                  return null;
              }
    
              if (head.next == null){
        
                  return new TreeNode(head.val);
              }
    
              ListNode fast = head, slow = head, pre = head;
              while (fast != null && fast.next != null){
        
                  fast = fast.next.next;
                  pre = slow;
                  slow = slow.next;
              }
              pre.next = null;
              TreeNode node = new TreeNode(slow.val);
    
              node.left = sortedListToBST(head);
              node.right = sortedListToBST(slow.next);
              return  node ;
        }
    }

![在这里插入图片描述][20200626202518315.png]  
使用半开半闭区间

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
            public   TreeNode sortedListToBST(ListNode head) {
        
              return  helper(head,  null) ;
        }
    
    
        private TreeNode helper(ListNode head, ListNode tail){
        
            if (head == tail){
        
                return null;
            }
    
            ListNode fast = head, slow = head;
            while (fast != tail && fast.next != tail){
        
                slow = slow.next;
                fast = fast.next.next;
            }
            
            TreeNode node = new TreeNode(slow.val);
            node.left = helper(head, slow);
            node.right = helper(slow.next, tail);
            return node;
        }
    }

![在这里插入图片描述][20200626205425717.png]

## 转换为数组然后BST ##

索引作为参数，就是参数，不要一下子长度一下子索引

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private  ArrayList<Integer> arrayList;
    
        public Solution() {
        
            arrayList = new ArrayList<>();
        }
    
        // 转换为数组，然后转为BST
        public  TreeNode sortedListToBST(ListNode head) {
        
              while (head != null){
        
                  arrayList.add(head.val);
                  head = head.next;
              }
              return  arrayListToBST(0,  arrayList.size() - 1) ;
        }
        
        public  TreeNode arrayListToBST(int left, int right){
        
            if (right < left){
        
                return null;
            }
            
            int mid = left + (right - left)/2;
            TreeNode node = new TreeNode(arrayList.get(mid));
            node.left = arrayListToBST(left, mid - 1);
            node.right = arrayListToBST(mid + 1, right);
            return node;
        }
    }

![在这里插入图片描述][20200626204643890.png]

## 中序遍历模拟 ##

因为我们知道题目给定的升序数组，其实就是二叉搜索树的中序遍历。那么我们完全可以按照这个顺序去为每个节点赋值。

实现的话，我们套用中序遍历的递归过程，并且将start和end作为递归参数，当start == end的时候，就返回null

先回想一下中序遍历的算法

public List<Integer> inorderTraversal(TreeNode root) {
        
        List<Integer> ans = new ArrayList<>();
        getAns(root, ans);
        return ans;
    }
    
    private void getAns(TreeNode node, List<Integer> ans) {
        
        if (node == null) {
        
            return;
        }
        getAns(node.left, ans); 
        ans.add(node.val);
        getAns(node.right, ans);
    }

之前是将node和val进行保存，这里的话我们是给当前节点仅需赋值，为了实现一次赋值，我们需要一个cur指针指向给定的数列，每赋一个值就进行后移。

ListNode cur = null;
    
    public TreeNode sortedListToBST(ListNode head) {
        
        cur = head;
        int end = 0;
        while (head != null) {
        
            end++;
            head = head.next;
        }
        return sortedArrayToBSTHelper(0, end);
    }
    
    private TreeNode sortedArrayToBSTHelper(int start, int end) {
        
        if (start == end) {
        
            return null;
        }
        int mid = (start + end) >>> 1;
        //遍历左子树并且将根节点返回
        TreeNode left = sortedArrayToBSTHelper(start, mid);
        //遍历当前根节点并进行赋值
        TreeNode root = new TreeNode(cur.val);
        root.left = left;
        cur = cur.next; //指针后移，进行下一次的赋值
        //遍历右子树并且将根节点返回
        TreeNode right = sortedArrayToBSTHelper(mid + 1, end);
        root.right = right;
        return root;
    }

![在这里插入图片描述][20200626211040431.png]

[109.]: https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200626212439697.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[108.]: https://blog.csdn.net/zhizhengguan/article/details/106757745
[20200626202518315.png]: https://img-blog.csdnimg.cn/20200626202518315.png
[20200626205425717.png]: https://img-blog.csdnimg.cn/20200626205425717.png
[20200626204643890.png]: https://img-blog.csdnimg.cn/20200626204643890.png
[20200626211040431.png]: https://img-blog.csdnimg.cn/20200626211040431.png