# Easy understanding c++ O(n) time, O(1) space.

• Too many post to dig out if anyone has same idea.

Three step. each step is O(n) time.

1. Get the number of nodes.

2. make a balanced tree. (pre-order, bfs)

3. assign values. (in-order, dfs)

codes:

``````    TreeNode* sortedListToBST(ListNode* head) {
if (head == NULL) return NULL;
// get list size
int n = 0;
while (scan) {
n++; scan = scan->next;
}
// make balance tree
TreeNode * root = makeTree(n);
//assign values
return root;
}
ListNode * inorder(TreeNode *root, ListNode * node) {
if (root->left != NULL) node = inorder(root->left, node);
root->val = node->val;
node = node->next;
if (root->right != NULL) node = inorder(root->right, node);
return node;
}

TreeNode* makeTree(int n) {
TreeNode * root = new TreeNode(0);
queue<TreeNode *> q;
q.push(root);
n--;
while (true) {
if (n == 0) break;
TreeNode *x = q.front();
q.pop();
x->left = new TreeNode(0);
q.push(x->left);
n--;
if (n == 0) break;
x->right = new TreeNode(0);
q.push(x->right);
n--;
if (n == 0) break;
}
return root;
}``````

• step2 make a balanced tree, means o(n) space not o(1), although I agree it is a must.

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