如何將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)

1.對(duì)有序數(shù)組或者有序鏈表來(lái)說(shuō)，把中間節(jié)點(diǎn)當(dāng)作根節(jié)點(diǎn)2. 左邊數(shù)組的值都小于根節(jié)點(diǎn)，作為左子樹(shù)； 右邊數(shù)組的值都大于根節(jié)點(diǎn)，作為右子樹(shù)。3. 遞歸處理左子樹(shù)和右子樹(shù)，一直到只剩下一個(gè)節(jié)點(diǎn)。

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func sortedArrayToBST(nums []int) *TreeNode {    if len(nums) == 0 {        return nil    }    mid := len(nums)/2    root := new(TreeNode)    root.Val = nums[mid]    root.Left = sortedArrayToBST(nums[:mid])    root.Right = sortedArrayToBST(nums[mid+1:])    return root}// 算法：核心思想是利用二分法，對(duì)有序數(shù)組來(lái)說(shuō)，把中間節(jié)點(diǎn)當(dāng)作根節(jié)點(diǎn)，// 左邊數(shù)組的值都小于根節(jié)點(diǎn)，作為左子樹(shù)；// 右邊數(shù)組的值都大于根節(jié)點(diǎn)，作為右子樹(shù)。// 遞歸處理左子樹(shù)和右子樹(shù)，一直到只剩下一個(gè)節(jié)點(diǎn)。

/** * Definition for singly-linked list. * type ListNode struct { *     Val int *     Next *ListNode * } *//** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func sortedListToBST(head *ListNode) *TreeNode {    if head == nil {        return nil    }    if head.Next == nil {        return &TreeNode{Val:head.Val}            }    // 小技巧：方便一次循環(huán)找到中間節(jié)點(diǎn)的前序節(jié)點(diǎn)，哨兵    s := new(ListNode)     s.Next = head    f := head    for f != nil && f.Next != nil {         // 精髓：快慢指針，1步，2步正好是二等分，可以延伸出三等份，n等分        s = s.Next        f = f.Next.Next    }        res := new(TreeNode)    res.Val = s.Next.Val    r := s.Next.Next    s.Next = nil // 左半部分單獨(dú)成一個(gè)鏈表    res.Left = sortedListToBST(head)    res.Right = sortedListToBST(r)    return res}// 算法：利用二分法，這里是采用了鏈表二分法的常規(guī)做法，// 找到中間節(jié)點(diǎn)之后，將鏈表一分為二，左邊的繼續(xù)構(gòu)造左子樹(shù)，右邊的為右子樹(shù)// 遞歸處理，直到所有節(jié)點(diǎn)都處理完。