題目

給定一個二叉樹

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

填充它的每個 next 指針荧呐，讓這個指針指向其下一個右側(cè)節(jié)點(diǎn)唬复。如果找不到下一個右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。
初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL缚柳。
示例：

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

輸出：
{
    "$id": "1",
    "left": {
        "$id": "2",
        "left": {
            "$id": "3",
            "left": null,
            "next": {
                "$id": "4",
                "left": null,
                "next": {
                    "$id": "5",
                    "left": null,
                    "next": null,
                    "right": null,
                    "val": 7
                },
                "right": null,
                "val": 5
            },
            "right": null,
            "val": 4
        },
        "next": {
            "$id": "6",
            "left": null,
            "next": null,
            "right": {
                "$ref": "5"
            },
            "val": 3
        },
        "right": {
            "$ref": "4"
        },
        "val": 2
    },
    "next": null,
    "right": {
        "$ref": "6"
    },
    "val": 1
}

解釋：給定二叉樹如圖 A 所示埃脏，你的函數(shù)應(yīng)該填充它的每個 next 指針，以指向其下一個右側(cè)節(jié)點(diǎn)喂击，如圖 B 所示剂癌。

代碼及解釋

/*
// 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) {
        //cellEnd記錄這一層的結(jié)束節(jié)點(diǎn)是幾號
        //num記錄下一層的總節(jié)點(diǎn)數(shù)
        int cellEnd=1,num = 0;
        //如果為空或者沒有左右節(jié)點(diǎn)淤翔，返回原根節(jié)點(diǎn)
        if(!root || (!root->left && !root->right))
            return root;
        vector<Node*> list ;
        list.push_back(root);
        //利用層次遍歷的方式翰绊，給該層次非最后一個節(jié)點(diǎn)添加next屬性
        for(int i=0;i<list.size();i++){
            //如果有左節(jié)點(diǎn)，放進(jìn)去且記錄下一層的節(jié)點(diǎn)個數(shù)
            if(list[i]->left){
                list.push_back(list[i]->left);
                num++;
            }
            //如果有右節(jié)點(diǎn)旁壮，放進(jìn)去且記錄下一層的節(jié)點(diǎn)個數(shù)
            if(list[i]->right){
                list.push_back(list[i]->right);
                num++;
            }
            //不是層結(jié)束點(diǎn)
            if(i != (cellEnd-1)){
                list[i]->next = list[i+1];
            }
            //是該層的結(jié)束监嗜，則改變cellEnd的值代表下一層的結(jié)束標(biāo)志
            //同時重置層次記錄參數(shù)num
            else{
                cellEnd += num;
                num = 0;
            }
        }
        return root;
    }
};