[Leetcode] Convert sorted list to binary search tree 将排好的链表转成二叉搜索树

---恢复内容开始---

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

题目要求：转成高度平衡的二叉搜索树。

高度平衡的二叉搜索树：i)左子树和右子树的高度之差的绝对值不超过1; ii)树中的每个左子树和右子树都是AVL树; iii)每个节点都有一个平衡因子（balance factor bf）,任一节点的平衡因子是1,0，-1.（每个节点的平衡因子等于右子树的高度减去左子树的高度） .

方法一：使用快慢指针

思路：若是一升序的数组，则取中间元素，作为根节点，然后以此方法分别去构成处左右子树。但链表没有办法直接访问其中间的结点，怎么办？可以通过快慢指针的方式，当快指针到链表结尾时，慢指针刚好到链表的中间来实现找到中间结点的目的。然后用递归的方法构造树。代码如下：

 /**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     ListNode *next;

  *     ListNode(int x) : val(x), next(NULL) {}

  * };

  */

 /**

  * Definition for binary tree

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

 public:

     TreeNode *sortedListToBST(ListNode *head)

     {

         if(head==NULL)  return NULL;

         if(head->next==NULL)    return new TreeNode(head->val);

         ListNode *fast=head;

         ListNode *slow=head;

         ListNode *preSlow=NULL;    

         while(fast&&fast->next)

         {

             preSlow=slow;

             slow=slow->next;

             fast=fast->next->next;

         }

         TreeNode *root=new TreeNode(slow->val);

         preSlow->next=NULL;

         root->left=sortedListToBST(head);

         root->right=sortedListToBST(slow->next);

         return root;

     }

 };

代码中值得注意的：一、只有一个结点时返回值的写法；二、使用快慢指针时，前半段要比后半段多；三、链表分成两条时，注意在结尾压入NULL，形成两条。

方法二：使用结点的个数一分为二

可以按照类似中序遍历的做法，首先，创建当前节点的左孩子，然后创建当前节点，将该节点的left指针指向之前创建好的左孩子，然后创建右孩子，以这样的顺序，每次新创建的节点都对应单链表的顺序遍历中当前位置的节点，因此，用一个全局遍历表示当链表，在递归过程中不断修改当前单链表的指针，使每次创建的节点与单链表头节点对应。这里的start和end使用来作为终止条件

class Solution {

public:

    TreeNode *sortedListToBST(ListNode *head)

    {

        int len=;

        ListNode *node=head;

        while(node !=NULL)

        {

            node=node->next;

            len++;

        }

        return rebuildBST(head,,len-);

    }

    TreeNode *rebuildBST(ListNode *&node,int start,int end)

    {

        if(start>end)   return NULL;

        //防止内存泄漏 mid=start+(end-start)/2;但是测试{1,3}（为偶数）用例通不过

        int mid=(start+end+)>>;

        TreeNode *leftChild=rebuildBST(node,start,mid-);

        TreeNode *parent=new TreeNode(node->val);

        parent->left=leftChild;

        node=node->next;

        parent->right=rebuildBST(node,mid+,end);

        return parent;

    }

};

巴特西

[Leetcode] Convert sorted list to binary search tree 将排好的链表转成二叉搜索树

最新文章

热门文章