首页 > 代码库 > leetcode Convert Sorted List to Binary Search Tree

leetcode Convert Sorted List to Binary Search Tree

把一个有序链表构成成平衡二叉树。和上一题有一点像。

思路一:将有序链表存在一个数组里。然后根据每次访问中间节点当做根节点递归左右子树节点即可。代码如下:

/** * 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 *sortedArrayTree(vector<int> arr, int start, int end)    {        if (start > end) return NULL;            TreeNode *root = new TreeNode(arr[(start + end)/2]);            root -> left = sortedArrayTree(arr, start, (start + end)/2 - 1);        root -> right = sortedArrayTree(arr, (start + end)/2 + 1, end);        return root;    }        // 给定有序链表,构造高度平衡二叉树    TreeNode *sortedListToBST(ListNode *head)    {        if (!head) return NULL;            vector<int> tmp;        while(head)        {            tmp.push_back(head -> val);            head = head -> next;        }        return sortedArrayTree(tmp, 0, tmp.size() - 1);    }};

思路和做法应该是对的,但是Memory Limit Exceeded了,说明不能用数组存,没有那么大的空间,那就之间在链表上操作。是否记得我们在Construct Binary Tree from Inorder and Postorder Traversal中也遇到过Memory Limit的问题。那里也是应为开辟的空间有点大了。

其实巧妙的是,我发现如果我们这里把传入的arr当做应用传入,也就是vector<int> &arr的话,就可以Accept。不信你改改试试。不过我们还是再想想,直接链表上怎么操作吧。

这个是用两个链表节点递归的,节点相同就返回null,找中间节点用代码中的while操作,java代码如下:

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; next = null; } * } *//** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public TreeNode sortedListToBST(ListNode head) {        return rec(head, null);    }        public TreeNode rec(ListNode start, ListNode end) {        if(start == end) {            return null;        }        ListNode p = start, q = start;        while(q != end && q.next != end) {            p = p.next;            q = q.next.next;        }                TreeNode root = new TreeNode(p.val);        root.left = rec(start, p);        root.right = rec(p.next, end);                return root;    }    }

这个是用传入长度,然后找到中间节点:

/** * 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) {        int n=0;        ListNode *p=head;        while(p!=NULL)n++,p=p->next;        return build(head,n);            }    TreeNode *build(ListNode *head,int n)    {        if(head==NULL||n==0)return NULL;        ListNode *p=head;        for(int i=1;i<(n+1)/2;++i)p=p->next;        TreeNode *root=new TreeNode(p->val);        root->left=build(head,(n+1)/2-1);        root->right=build(p->next,n-(n+1)/2);    }};

leetcode上讨论组的最佳解法是自底向上的:

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {  if (start > end) return NULL;  // same as (start+end)/2, avoids overflow  int mid = start + (end - start) / 2;  BinaryTree *leftChild = sortedListToBST(list, start, mid-1);  BinaryTree *parent = new BinaryTree(list->data);  parent->left = leftChild;  list = list->next;  parent->right = sortedListToBST(list, mid+1, end);  return parent;} BinaryTree* sortedListToBST(ListNode *head, int n) {  return sortedListToBST(head, 0, n-1);}

 

leetcode Convert Sorted List to Binary Search Tree