C#: Two Simple Solutions with Explanation (Accepted)


  • 0

    Solution 1: Not using constant space here but trying to show a very simple intuitive solution.

            public void Connect(TreeLinkNode root)
            {
                Dictionary<int, List<TreeLinkNode>> levelMap = new Dictionary<int, List<TreeLinkNode>>();
                ConnectHelper(root, 0, ref levelMap);
                foreach (int key in levelMap.Keys)
                {
                    List<TreeLinkNode> curr = levelMap[key];
                    int i = 0;
                    for (; i < curr.Count - 1; i++)
                        curr[i].next = curr[i + 1];
                    curr[i].next = null;
                }
            }
    
            private static void ConnectHelper(TreeLinkNode root, int level, ref  Dictionary<int, List<TreeLinkNode>> levelMap)
            {
                if (null == root) return;
                if (!levelMap.Keys.Contains(level)) levelMap[level] = new List<TreeLinkNode>();
                levelMap[level].Add(root);
                ConnectHelper(root.left, level + 1, ref levelMap);
                ConnectHelper(root.right, level + 1, ref levelMap);
            }
    

    Solution 2: Constant Space solution with Explanation.

    public void Connect(TreeLinkNode root)
        {
            TreeLinkNode tempHead = new TreeLinkNode(0);  //Temp head of linked list.
            TreeLinkNode pointer = tempHead;              //Just a pointer, currently pointing to tempHead.
            while (root != null)
            {
                if (root.left != null)
                {
                    pointer.next = root.left;    //(pointer -> tempHead) tempHead.next is the starting node of next level.
                    pointer = pointer.next;
                }
                if (root.right != null)
                {
                    pointer.next = root.right;
                    pointer = pointer.next;
                }
                root = root.next;
                if (root == null && pointer != tempHead) //Check if its last node of the level and pointer != tempHead
                {
                    root = tempHead.next;  //Need to shift to next level. tempHead.next points to the 1st node on next level.
                    pointer = tempHead;    //Pointer going back to tempHead. 
                }
            }
        }
    

Log in to reply
 

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