LeetCode: Populating Next Right Pointers in Each Node Solution
BFS with levelApproach: BFS
Breadth-first traversal
Grab all nodes with the same level and work on them
Implementation
1var connect = function (root) {2 if (!root) return null34 let queue = []5 let accLevel = 067 const addLevel = (node, level = 0) => {8 if (!node) return9 node.level = level10 addLevel(node.left, level + 1)11 addLevel(node.right, level + 1)12 }1314 addLevel(root)1516 queue.push(root)1718 while (queue.length > 0) {19 const nodes = []2021 while (queue.length > 0 && queue[0].level === accLevel) {22 nodes.push(queue.shift())23 }2425 for (let i = 0; i < nodes.length; i++) {26 nodes[i].next = nodes[i + 1] || null27 if (nodes[i].left) {28 queue.push(nodes[i].left, nodes[i].right)29 }30 }3132 accLevel++33 }3435 return root36}
Approach: Recursive
The most important part is to connect
next
of 2 subtreesImplementation
1var connect = function (root) {2 if (!root) return null3 if (!root.left) return root45 root.left.next = root.right6 if (root.next) {7 root.right.next = root.next.left8 }9 connect(root.left)10 connect(root.right)1112 return root13}
Comments
Loading comments...
Tags
leetcode
tree
binary tree
bfs
recursion
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.