Sharing a Simple Java Iterative Solution


  • 1
    V

    To solve this problem uses BFS algorithm.

    However, the BFS need to use queue to store all the nodes of current level; it will use O(n) space. To achieve O(1) space here, we just need to keep tracking of first node of each level. The next pointer will lead us find the next node.

    public class Solution {
        public void connect(TreeLinkNode root) {
            TreeLinkNode leftmostNode = root;
            while (leftmostNode != null) {
                TreeLinkNode node = leftmostNode;
                TreeLinkNode dummy = new TreeLinkNode(0);
                TreeLinkNode prev = dummy;
                while (node != null) {
                    if (node.left != null) {
                        prev.next = node.left;
                        prev = prev.next;
                    }
                    if (node.right != null) {
                        prev.next = node.right;
                        prev = prev.next;
                    }
                    node = node.next;
                }
                leftmostNode = dummy.next;
            }
        }
    }

Log in to reply
 

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