Leetcode.116.Populating Next Rig

题目

给定一个完美二叉树, 树节点包含3个指针, 一个指向左子树, 一个指向右子树, 一个指向右边水平的节点.

                   1                                1 -> null
                 /   \                             /  \
                2     3                          2  ->  3 -> null
              /   \  /  \                      /  \    /  \
              4   5 6    7                    4 -> 5 -> 6 -> 7 -> null

思路

递归, 找规律. 发现left->next: super->right , right->next: super->next->left.
对左右子树分开处理.

Node* connect(Node* root) {
    if(root == nullptr) return nullptr;
    if (root->left != nullptr) {
        root->left->next = root->right;
    }
    if (root->right != nullptr && root->next != nullptr) {
        root->right->next = root->next->left;
    }

    connect(root->left);
    connect(root->right);

    return root;
}

总结

仔细思考, 找出数学公式. 递归都是有一个公式的, 先写出伪代码, 代码就呼之欲出了.