Simple C++ Recursion With Comments


  • 2
    G
        void connect(TreeLinkNode *root) {
            if (!root) return;
            if (root->left) {
                if (root->right) root->left->next = root->right;    // if root has right, then that will be left's next
                else root->left->next = find_next(root->next);      // else, walk the root level's next chain
            }
            if (root->right) root->right->next = find_next(root->next); // walk the root level's next chain
            // note that we need to recurse on right first
            if (root->right) connect(root->right);
            if (root->left) connect(root->left);
        }
    
        TreeLinkNode* find_next(TreeLinkNode *root) {
            // walk the root level's next chain until the end or we find such a node that has at least one child
            while (root && !root->left && !root->right) {
                root = root->next;
            }
            if (root) return root->left ? root->left : root->right;
            else return NULL;
        }
    

  • 0
    L

    why should we recurse to right first?
    It will be wrong if i change the order, but please tell me why ?


  • 0

    @liu-yu

    why should we recurse to right first?
    It will be wrong if i change the order, but please tell me why ?

    Make sure to do recursion on right tree first because for each level, we need right nodes have all their next pointers populated before moving to left nodes on the same level. And this is what the loop in helper method find_next does:

    while (root && !root->left && !root->right) {
                root = root->next;
            }
    

    What it does is the fact if a node root does not have a right sibling, then x's parent's next non-leaf node's left-most child must be x's next node. That means the algorithm has to guarantee:

    1. Next pointers of parents have to be populated before children's (DFS already guaranteed).
    2. Next pointers of far right nodes have to be populated before left ones on a same level (Right recursion has to come before left one).

  • 0
    G

    @liu-yu

    We need to recurse on the right child first to be able to handle the case when we are trying to set the next of a left child whose parent does not have a right child. In this case, we need to walk the parent's next chain, right? For this chain to be valid it should already be populated and that won't happen if we have not recursed right first.

    I hope that's helpful. You should be able to work a few examples to understand it better.


Log in to reply
 

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