109.md

✏️Leetcode基础刷题之(109. Convert Sorted List to Binary Search Tree)

2019-02-27 吴亲库里 库里的深夜食堂

---

✏️描述

给定一个单链表,其中的元素按升序排序,把他转换为高度平衡的二叉查找树

---

✏️题目实例

给定一个单链表[-10,-3,0,5,9],那么他的答案是[0,-3,9,-10,null,5]

---

✏️题目分析

将有序的链表存入数组中,然后不断的寻找中点,构建左右树

function sortedListToBST($head) {
        $nums=[];
        if(!$head){
            return;
        }
        while($head !==null){
              array_push($nums,$head->val);
            $head=$head->next; 
        }
       
    return  $this->sortedArrayToBST($nums);
    }
    
      function sortedArrayToBST($nums) {
        if(!$nums){
            return;
        }
        $mid=floor(count($nums) / 2);
        $root=new TreeNode($nums[$mid]);
        $root->left=$this->sortedArrayToBST(array_slice($nums,0,$mid));
        $root->right=$this->sortedArrayToBST(array_slice($nums,$mid+1));
        return $root;
    }

---

✏️另一种解题

另一种方法.叫做快fast,慢slow指针.每次快指针走两步,慢指针走一步,这样slow指针总是指向中点,然后构建左右子树,以下具体实现,不过两种的实现方式都是递归的思想.把大问题化成相似的小问题来解决.

 /**
     * @param ListNode $head
     * @return TreeNode
     */
    function sortedListToBST($head) {
      if(!$head){
          return;
      }
        return $this->help($head,null);
    }
    function help($head,$tail){
        if($head==$tail){
            return ;
        }
        $slow=$head;
        $fast=$head;
        while($fast !== $tail && $fast->next !==$tail){
            $fast=$fast->next->next;
            $slow=$slow->next;
        }
        $root=new TreeNode($slow->val);
        $root->left=$this->help($head,$slow);
        $root->right=$this->help($slow->next,$tail);
        return $root;
    }

---

联系

​