What's wrong with my straight forward answer?


  • 0
    B
    void connectMiddle(TreeLinkNode *rootLeft, TreeLinkNode *rootRight)
    {
        if (rootLeft->right && rootRight->left)
    	    rootLeft->right->next = rootRight->left;
    }
    
    void connect(TreeLinkNode *root)
    {
        TreeLinkNode *tmp = root;
    	if (root && root->left && root->right)
    	{
    		root->left->next = root->right;
    		connect(root->left);
    		connect(root->right);
    		tmp = root->left;
    		while (tmp->next)
    		{
        		connectMiddle(tmp, tmp->next);
        		tmp = tmp->next;
    		}
    	}
    }
    

    I am assuming the tree is perfect as noted... but it seems like the serialization didn't convince me that it is a perfect tree. Please let me know where I got it wrong. Thanks!


  • 2
    M

    It is very straightforward, but you are making a slight mistake. You are making the connections as if your algorithm uses a level-order traversal of the nodes, while it actually is using a DFS. The right node's children will all be fully fleshed out before right.next is ever set, so its right hand children's nexts will be null instead of connecting to their rightward cousins.

    I'm pretty sure simply moving the connect calls after the while loop's end will fix this. As a side note, since it is known that there are literally no holes in the tree, you do not need the while loop. An if is sufficient.

    public void connect(TreeLinkNode root) {
        if(root == null) return;
        if(root.left != null){
            root.left.next = root.right;
        }
        if(root.right != null && root.next != null){
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }

  • 0
    O

    Mike, will your answer miss out the connection to null at the end of each level?


  • 0
    M

    No, the "connection to null" is already present. You only have to correct the next pointers in the middle.


Log in to reply
 

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