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


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

129fd2cf0d4ea727f876f3cfeb452323.png

     题目介绍

   给,,把它树。

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


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


   还 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;
    }

运行结果


fb41a86ddeb8390c468572b501b16afc.png


要是看到了别人用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;
    }

吴亲库里 has written 86 articles

情绪只是对自己无能的愤怒

积分:4182 等级:P8 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?