Leetcode之(109. Convert Sorted List to Binary )

Leetcode · curry · 于 24天前 发布 · 24 次阅读

###题目介绍

这里我的想法是先把链表转换为数组,找出最中间的位置为根节点,(为了满足高度差的绝对值小 于等于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;
    }

本文由 curry 创作,采用 知识共享署名 3.0 中国大陆许可协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

共收到 0 条回复 二叉树 php 算法
没有找到数据。
添加回复 (需要登录)
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册
吴亲库里的深夜食堂