[Leetcode] Convert Sorted Array/List to Binary Sea

wpw 發(fā)布于2019-08-14 12:40 / 773人閱讀

摘要：我們可以用和兩個(gè)值來限定子樹在鏈表中的位置，通過遞歸的方式，深入找到最左邊，然后開始順序遍歷鏈表鏈表當(dāng)前節(jié)點(diǎn)作為全局變量，這樣無論遞歸在哪我們都能拿到，同時(shí)建樹。代碼先遞歸的計(jì)算左子樹創(chuàng)造根節(jié)點(diǎn)最后遞歸的計(jì)算右子樹

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

遞歸法 復(fù)雜度

時(shí)間 O(N) 空間 O(H)

思路

首先先分析下題目，二叉搜索樹，有序鏈表，之間有什么關(guān)系？我們知道二叉搜索樹做深度優(yōu)先搜索就可以從小到大順序讀取樹中節(jié)點(diǎn)，但是如何從一串有序的數(shù)字還原二叉搜索樹呢？仔細(xì)觀察的話可以發(fā)現(xiàn)，該串?dāng)?shù)字的中點(diǎn)應(yīng)該就是整棵樹的根，然后該根節(jié)點(diǎn)的左子樹的根節(jié)點(diǎn)，又是左半邊的中點(diǎn)，該根節(jié)點(diǎn)的右子樹的根節(jié)點(diǎn)，又是右半邊的中點(diǎn)，以此往復(fù)，鏈表第一個(gè)節(jié)點(diǎn)，就是最左邊左“子樹”的根節(jié)點(diǎn)（實(shí)際上已經(jīng)是葉子節(jié)點(diǎn)了，但先看成只有一個(gè)節(jié)點(diǎn)的子樹，最左邊左子樹的左節(jié)點(diǎn)和右節(jié)點(diǎn)都是空）。我們可以用start和end兩個(gè)值來限定子樹在鏈表中的位置，通過遞歸的方式，深入找到最左邊，然后開始順序遍歷鏈表（鏈表當(dāng)前節(jié)點(diǎn)作為全局變量，這樣無論遞歸在哪我們都能拿到），同時(shí)建樹。

代碼

public class Solution {
    
    ListNode curr;
    
    public TreeNode sortedListToBST(ListNode head) {
        curr = head;
        int len = 0;
        // 先計(jì)算出鏈表的長度
        while(head != null){
            head = head.next;
            len++;
        }
        curr = head;
        // 開始建樹
        return buildTree(0, len - 1);
    }
    
    private TreeNode buildTree(int start, int end){
        // 如果start>end，說明子樹已經(jīng)小到?jīng)]有節(jié)點(diǎn)了，直接返回null
        if(start > end){
            return null;
        }
        // 找到中點(diǎn)
        int mid = start + (end - start) / 2;
        // 先遞歸的計(jì)算左子樹
        TreeNode left = buildTree(start, mid - 1);
        // 然后建立根節(jié)點(diǎn)
        TreeNode root = new TreeNode(curr.val);
        // 鏈表順序遍歷
        curr = curr.next;
        // 最后計(jì)算右子樹
        TreeNode right = buildTree(mid + 1, end);
        // 將三個(gè)節(jié)點(diǎn)連接起來
        root.left = left;
        root.right = right;
        return root;
    }
}

2018/10

var curr *ListNode

func buildTree(start int, end int) *TreeNode {
    if start > end {
        return nil
    }
    mid := start + (end-start)/2
    root := &TreeNode{}
    root.Left = buildTree(start, mid-1)
    root.Val = curr.Val
    curr = curr.Next
    root.Right = buildTree(mid+1, end)
    return root
}

func sortedListToBST(head *ListNode) *TreeNode {
    length := 0
    curr = head
    for curr != nil {
        curr = curr.Next
        length++
    }
    curr = head
    return buildTree(0, length-1)
}

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

遞歸法 復(fù)雜度

時(shí)間 O(N) 空間 O(H)

思路

和用鏈表建樹的思路相似，實(shí)現(xiàn)更加簡單，因?yàn)閿?shù)組支持隨機(jī)查詢，我們可以直接訪問中點(diǎn)而無須遍歷鏈表。

代碼

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }
    
    private TreeNode buildTree(int[] nums, int start, int end){
        if(start > end){
            return null;
        }
        int mid = start + (end - start) / 2;
        // 先遞歸的計(jì)算左子樹
        TreeNode left = buildTree(nums, start, mid - 1);
        // 創(chuàng)造根節(jié)點(diǎn)
        TreeNode root = new TreeNode(nums[mid]);
        // 最后遞歸的計(jì)算右子樹
        TreeNode right = buildTree(nums, mid + 1, end);
        root.left = left;
        root.right = right;
        return root;
    }
}