Time: 25 minutes
The main idea is to use the stack. The difference from the ordinary level-order traversal is that the stack is cleared every time
var connect = function(root) {
if (!root) return null var stack = [root]
while(stack.length) {
var _stack = [...stack,null]
stack = []
var pre = _stack.shift()
while(_stack.length || pre) {
pre.left && stack.push(pre.left)
pre.right && stack.push(pre.right)
pre.next = _stack.shift()
pre = pre.next }
}
return root};Obviously, the memory space of On I used does not meet the constant space requirement of the question, considering that the links of each layer can be found in the form of a linked list by relying on the parent node.
while(pre) {
var cur = pre
while(cur) {
cur.left.next = cur.right cur.right.next = cur.next.left cur = cur.next }
}The remaining things to consider are
- Pre needs to be saved as the leftmost node to facilitate subsequent linked list connections.
- Next is empty on the first level.
- The last level has no left or right nodes.
Time: 25 minutes
The main idea is to use the stack. The difference from the ordinary level-order traversal is that the stack is cleared every time
var connect = function(root) {
if (!root) return null var stack = [root]
while(stack.length) {
var _stack = [...stack,null]
stack = []
var pre = _stack.shift()
while(_stack.length || pre) {
pre.left && stack.push(pre.left)
pre.right && stack.push(pre.right)
pre.next = _stack.shift()
pre = pre.next }
}
return root};Obviously, the memory space of On I used does not meet the constant space requirement of the question, considering that the links of each layer can be found in the form of a linked list by relying on the parent node.
while(pre) {
var cur = pre
while(cur) {
cur.left.next = cur.right cur.right.next = cur.next.left cur = cur.next }
}The remaining things to consider are
- pre needs to be saved as the leftmost node to facilitate subsequent linking in a linked list.
- The next field on the first level is empty.
- The last level has no left or right nodes.