Populating Next Right Pointers in Each Node 題解

原創(chuàng)文章，拒絕轉(zhuǎn)載

題目來源：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();}}} };

---

解題描述

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

轉(zhuǎn)載于:https://www.cnblogs.com/yanhewu/p/8041064.html

總結(jié)

以上是生活随笔為你收集整理的[Leetcode Week15]Populating Next Right Pointers in Each Node的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。