466. 使用快慢指針把有序鍊表轉換二叉搜索樹

想了解更多數據結構以及算法題，可以關注微信公眾號「數據結構和算法」，每天一題為你精彩解答。

問題描述

給定一個單鍊表，其中的元素按升序排序，將其轉換為高度平衡的二叉搜索樹。

本題中，一個高度平衡二叉樹是指一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過 1。

示例:

1，快慢指針解決

二叉搜索樹的特點是當前節點大於左子樹的所有節點，並且小於右子樹的所有節點，並且每個節點都具有這個特性。

題中說了，是按照升序排列的單鍊表，我們只需要找到鍊表的中間節點，讓他成為樹的根節點，中間節點前面的就是根節點左子樹的所有節點，中間節點後面的就是根節點右子樹的所有節點，然後使用遞歸的方式再分別對左右子樹進行相同的操作……

這裡就以鍊表1→2→3→4→5為例來畫個圖看一下

我們看到上面鍊表的中間節點3就是二叉搜索樹的根節點，然後再對左右子節點以同樣的方式進行操作……，最後再來看下代碼

public TreeNode sortedListToBST(ListNode head) { //邊界條件的判斷 if (head == null) return null; if (head.next == null) return new TreeNode(head.val); //這裡通過快慢指針找到鍊表的中間結點slow，pre就是中間 //結點slow的前一個結點 ListNode slow = head, fast = head, pre = null; while (fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; } //鍊表斷開為兩部分，一部分是node的左子節點，一部分是node //的右子節點 pre.next = null; //node就是當前節點 TreeNode node = new TreeNode(slow.val); //從head節點到pre節點是node左子樹的節點 node.left = sortedListToBST(head); //從slow.next到鍊表的末尾是node的右子樹的結點 node.right = sortedListToBST(slow.next); return node;}

2，通過集合list解決

實際上還可以把鍊表中的值全都存儲到集合list中，每次把list分為兩部分，和上面原理一樣

public TreeNode sortedListToBST(ListNode head) { List<Integer> list = new ArrayList<>(); //把鍊表節點值全部提取到list中 while (head != null) { list.add(head.val); head = head.next; } return sortedListToBSTHelper(list, 0, list.size() - 1);}TreeNode sortedListToBSTHelper(List<Integer> list, int left, int right) { if (left > right) return null; //把list中數據分為兩部分 int mid = left + (right - left) / 2; TreeNode root = new TreeNode(list.get(mid)); root.left = sortedListToBSTHelper(list, left, mid - 1); root.right = sortedListToBSTHelper(list, mid + 1, right); return root;}

總結

做這道題我們首先要明白什麼是二叉搜索樹，這題是讓把升序的鍊表轉化為二叉搜索樹，如果是把升序的數組轉化為二叉搜索樹可能就更容易些了，但不管是什麼數據結構，最終實現原理還是一樣的。