题目:Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
思路:
这道题的解题思路和一样.我们也是找到有序链表的中间节点作为根,将有序链表分为两部分,再分别在左右两部分寻找中间节点作为根,递归下去构建 AVL 树.针对链表,我们不能通过坐标直接得到中间值,需要遍历链表,找到中间元素.创建辅助函数,TreeNode* sortedListToBST_helper(ListNode* head, int len), 参数 len 表示链表的长度.我们通过计算从头结点到中间节点的步数,来遍历链表,找到中间节点.递归终止条件,len <= 0.
Attention:
1. 一定要注意 while 和 if,不要顺手就写 if.
ERROR:
if (p - >next != NULL) {
p = p - >next;
len++;
}
2. len:表示链表的长度;
mid:表示从头节点到中间节点的节点个数(包括中间节点)(mid = (len+1)/2);
i : 表示头结点到中间节点的步数(i = mid -1);
3. 注意下次递归的头结点和链表长度设置.
root - >left = sortedListToBST_helper(head, mid - 1);
root - >right = sortedListToBST_helper(midp - >next, len - mid);
复杂度:AVL 树总共有 lgN 层,每层递归调用需要遍历 N/2 个元素,遍历链表,找到中间元素,将该元素作为根结点时间复杂度为 O(Nlg(N))
AC Code:
/**
* 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;
ListNode * p = head;
int len = 1;
while (p - >next != NULL) {
p = p - >next;
len++;
}
return sortedListToBST_helper(head, len);
}
private: TreeNode * sortedListToBST_helper(ListNode * head, int len) {
if (len <= 0) return NULL;
int mid = (len + 1) / 2; //计算从头结点到中间节点的有多少个节点(包含中间节点)
ListNode * midp = head;
//找到中间节点
int i = mid - 1;
while (i > 0) {
midp = midp - >next;
i--;
}
TreeNode * root = new TreeNode(midp - >val);
root - >left = sortedListToBST_helper(head, mid - 1);
root - >right = sortedListToBST_helper(midp - >next, len - mid);
return root;
}
};
这道题也可以利用
Tree (AVL 树)
Convert Sorted Array to Binary Search
中设置 start 和 end 来做;也可以先把 list 转成数组来做.
来源: http://lib.csdn.net/article/cplusplus/35994