# O(n) time O(1) space Morris In-Order Traversal solution

• ``````class Solution {
public:
return nullptr;

int max = 0;
for (ListNode *p = head; p != nullptr; p = p->next)
max++;

TreeNode* root = new TreeNode(1);

TreeNode* cur = root;
while (cur) {
int curleft = (cur->val) * 2;
if (curleft > max) { //cur->left == null, output current node, then go to right branch
cur->val = lp->val;
lp = lp->next;
cur = cur->right;
}
else {
if (cur->left == nullptr){
cur->left = new TreeNode(curleft);
}
TreeNode* prev = cur->left;
int prevright = (prev->val) * 2 + 1;
while (prev->right != cur && ((prev->right != nullptr)||(prevright <= max))/*prev->right != nullptr*/) {
if (prev->right == nullptr){
prev->right = new TreeNode(prevright);
}
prev = prev->right;
prevright = (prev->val) * 2 + 1;
}
if (prev->right != cur) {//prev->right == nullptr
prev->right = cur;
cur = cur->left;
}
else {
//output current node
int curright = (cur->val) * 2 + 1;
cur->val = lp->val;
lp = lp->next;
prev->right = nullptr;
if (curright <= max){
if (cur->right == nullptr) {
cur->right = new TreeNode(curright);
}
}
cur = cur->right;
}
}
}

return root;
}
};``````

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