[Leetcode Week15]Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node 題解

原創文章，拒絕轉載

題目來源：https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/

---

Description

Given a binary tree

struct TreeLinkNode {TreeLinkNode *left;TreeLinkNode *right;TreeLinkNode *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.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

Example

Given the following perfect binary tree,

1/  \2    3/ \  / \4  5  6  7

After calling your function, the tree should look like:

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

Solution

class Solution {
private:void connectNode(vector<TreeLinkNode*>& v) {int size = v.size();for (int i = 0; i <= size - 2; i++) {v[i] -> next = v[i + 1];}}
public:void connect(TreeLinkNode *root) {if (root == NULL)return;int levelNodeNum = 1;int curLevelNodeNum = 0;queue<TreeLinkNode*> q;vector<TreeLinkNode*> v;q.push(root);while (!q.empty()) {TreeLinkNode* node = q.front();q.pop();v.push_back(node);if (node -> left != NULL)q.push(node -> left);if (node -> right != NULL)q.push(node -> right);curLevelNodeNum++;if (curLevelNodeNum == levelNodeNum) {levelNodeNum *= 2;curLevelNodeNum = 0;connectNode(v);v.clear();}}}
};

---

解題描述

這道題是關于二叉樹層次遍歷問題的變種。題目給出的二叉樹是完全二叉樹，所以可以提前算出每一層的節點數目，因此來說還是相對比較容易的。所以基本的解決辦法是，使用一個隊列來存放節點。最開始將根節點加入隊列。每次從隊首取出一個節點，將其子節點加入隊尾。然后使用一個計數變量來計算當前層次上已經加入隊列的節點數目。一旦達到該層次的節點數目總和就對該層的節點進行next連接。