題目鏈接
tag:

• Medium；You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

question：
??Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Example:

Input: {"id":"2","left":{"id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

Output: {"id":"2","left":{"id":"4","left":null,"next":{"id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"ref":"5"},"next":null,"right":{"ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

思路：
??這道題實際上是樹的層序遍歷的應(yīng)用，既然是遍歷，就有遞歸和非遞歸兩種方法，最好兩種方法都要掌握，都要會寫。下面來看遞歸的解法，由于是完全二叉樹，所以若節(jié)點的左子結(jié)點存在的話，其右子節(jié)點必定存在，所以左子結(jié)點的next指針可以直接指向其右子節(jié)點，對于其右子節(jié)點的處理方法是，判斷其父節(jié)點的next是否為空，若不為空，則指向其next指針指向的節(jié)點的左子結(jié)點，若為空則指向NULL，代碼如下：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return NULL;
        if (root->left) root->left->next = root->right;
        if (root->right) root->right->next = root->next? root->next->left : NULL;
        connect(root->left);
        connect(root->right);
        return root;
    }
};