C++ solution with inorder tree walk


  • 1
    F
    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            int len = 0;
            ListNode *tmp = head;
            while(tmp) {
                len++;
                tmp = tmp->next;
            }
            
            tmp = head;
            ListNode **ptr = &tmp;
        
            if(len == 0) return NULL;
            
            return DFS(len, 0, ptr);
        }
        
        TreeNode * DFS(int len, int current, ListNode **curr) {
            
            TreeNode *node = new TreeNode(0);
            
            if(current * 2 + 1 <= len - 1) {
                node->left = DFS(len, current * 2 + 1, curr);
            }
    
            node->val = (*curr)->val;
            *curr = (*curr)->next;
            
            if(current * 2 + 2 <= len - 1) {
                node->right = DFS(len, current * 2 + 2, curr);
            }     
            
            return node;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.