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

2019-3-6 星期三   那么开始吧 不要关注排版，辣眼睛

     题目介绍

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

   首先我们来了解一下什么是二叉查找树。他的规则又是什么？

   二叉查找树，又叫二叉排序树，二叉搜索树。它可以是一棵空树，或者具有下面的性质：若它的左子树不为空，则它左子树上所有节点的值都小于他根节点的值。若它的右子树不为空，则它右子树上所有节点的值都大于他根节点的值。那么可以知道，它的左右子树也是二叉查找树。

   还需要注意的单词是 heightbalancedBST也就是高度平衡的二叉查找树,高度平衡就是每一节点      的两个子树的高度相差不能大于1。

  这里我的想法是先把链表转换为数组，找出最中间的位置为根节点,（为了满足高度差的绝对值小    于等于1）,这里转换为数组后获取中间点是0,他就是树的根节点,把数组左边到根节点之前的数作为他的左子树,根节点之后的数作为他的右子树。所以这里的左子树就是[-10,-3],右子树[0,5,9]，思路其实很清晰了,将有序的链表存入数组中,然后不断的寻找中点,构建左右树。最后的实现依然是递归。

最终实现

   /**

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

运行结果

主要是看到了别人用java写的一种思路.叫做快fast,慢slow指针.每次快指针走两步,慢指针走一步,以下是我参考别人java代码然后用php实现。

   /**
     * @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;
    }