109. Convert Sorted List to Bina

题目链接

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

代码

class Solution {
public:
    ListNode* head;
    int size(ListNode* head) {
        int cnt = 0;
        while (head != NULL) {
            cnt++;
            head = head->next;
        }
        return cnt;
    }

    TreeNode* dfs(int s, int e) {
        if (s > e) {
            return NULL;
        }

        int m = (s + e) / 2;
        TreeNode* left = dfs(s, m - 1);
        TreeNode* parent = new TreeNode(head->val);
        parent->left = left;
        head = head->next;
        parent->right = dfs(m + 1, e);
        cout<<parent->val<<endl;
        return parent;

    }
    TreeNode* sortedListToBST(ListNode* head) {
        this->head = head;
        int cnt = size(head);
        return dfs(0, cnt - 1);
    }
};