Very simple Java O(1) space, O(n) complexity iterative deepening DFS


  • 0
    J

    Each time, stop your dfs at a deeper level.
    Each time keep track of the last node of the target level that you encountered. Whenever you find a node of the target level (while walking the tree in order), update the last pointer.
    Whenever you search for a level and end up with last=null at the end, you are done.

    
    TreeLinkNode last;
        public void connect(TreeLinkNode root)
        {
            int lvl = 0;
            //do repeated inorder dfs of the tree, each time stopping at a deeper level
            while (true)
            {
                last = null;
                treeWalk(root, 0, lvl);
                //if we searcher for a level but did not find any nodes, we are done
                if (last == null)
                    break;
                lvl++;
            }
        }
        
        void treeWalk(TreeLinkNode root, int currLvl, int targetLvl)
        {
            //if we are at the target level, then update last pointer and stop recursion
            if (currLvl == targetLvl)
            {
                if (last != null)
                {
                    last.next = root;
                }
                last = root;
                return;
            }
            //if we are too high, do recursion to a lower level
            if (root.left != null)
            {
                treeWalk(root.left, currLvl+1, targetLvl);
            }
            if (root.right != null)
            {
                treeWalk(root.right, currLvl+1, targetLvl);
            }
        }
    

Log in to reply
 

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