[leetcode题解]109.Convert sorted list to binary search tree

leetcode 109,convert sorted list to binary search tree,给定一个已排好序的单链表,将其转换为一棵平衡二叉查找树,平衡二叉查找树要求左右子树的高度差小于等于1,而且左子树上的节点都小于等于当前根节点,有子树上的节点都大于当前根节点。

由于单链表本身就已经排好序了,所以,只要保证左右子树高度满足即可,可以以链表的中心节点为界,将链表一分为二,这样左右两边的节点个数差为1,左边的节点归到左子树上,右边的节点归到右子树上,然后这个中间节点作为根。然后对于左边和右边的部分递归的按照上述方法进行建树,最终建成的二叉树就是一棵平衡二叉搜索树。

这里用两种方法来做,c++使用了先把所有节点保存在一个vector中,然后可以o(1)的时间找到中间节点;python使用在链表中直接找中间节点的方法。

python代码:

class Solution(object):

    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        :author: 凌风技术站-iaccepted
        """
        return self.buildTree(head)

    def buildTree(self, head):
        if head is None:
            return None
        if head.next is None:
            return TreeNode(head.val)

        # 找到中心节点的前一个节点
        m = self.halfNode(head)

        t = m.next
        m.next = None
        m = t

        # 先生成根节点,然后递归的去建立左子树和右子树
        root = TreeNode(m.val)
        root.left = self.buildTree(head)
        root.right = self.buildTree(m.next)
        return root

    # 求单链表中间节点的方法
    def halfNode(self, head):
        if head is None or head.next is None:
            return head
        slow = head
        fast = head.next.next
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
        return slow

c++代码:

class Solution {
//author: 凌风技术站-iaccepted
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (head == NULL)return NULL;

        //先将所有的值存入一个vector,然后方便后面快速建树
        ivec.push_back(0);
        while(head != NULL)
        {
            ivec.push_back(head->val);
            head = head->next;
        }
        
        int n = ivec.size() - 1;
        TreeNode *root = buildTree(1, n);
        return root;
    }
    
private:
    //递归的建立整棵树
    TreeNode *buildTree(int l, int r)
    {
        if (l > r)return NULL;
        int mid = (l + r) >> 1;
        TreeNode *root = new TreeNode(ivec[mid]);
        root->left = buildTree(l, mid - 1);
        root->right = buildTree(mid + 1, r);
        return root;
    }
    vector<int> ivec;
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]109.Convert sorted list to binary search tree

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/74.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注