Populating Next Right Pointers in Each Node

原題鏈接Populating Next Right Pointers in Each Node

將完全二叉樹每個節點的next指針賦值，每個節點的next指針指向同一層的下一個節點，要求空間復雜度是O(1)

其實如果沒有空間復雜度的要求，可以使用層次遍歷，一種是使用隊列，為了控制層次可以在每層的節點后面向隊列追加一個空指針，另一種是遞歸，通過變量控制層數

既然有空間復雜度的限制，就不能使用額外的空間了。又因為肯定是需要從根節點開始設置next指針，所以如果某一時刻到達一個節點node，它所在的層數是h，那么可以確定的一點是，h-1層的next指針已經設置完畢。

這在某種程度上帶來了便利，因為可以根據h-1層的節點獲得第h層的所有節點，從而按照順序一個個設置next指針即可

到此可以確定，在遍歷的過程中(二叉樹肯定是遞歸)，需要同時記錄第h層的第一個節點和第h-1層的第一個節點。這樣，通過第h-1層的節點的next指針可以遍歷到h-1層的所有節點，又根據這些節點可以遍歷到第h層的所有節點

代碼如下

/*** Definition for binary tree with next pointer.* struct TreeLinkNode {* int val;* TreeLinkNode *left, *right, *next;* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}* };*/ class Solution { public:void connect(TreeLinkNode *root) {if(!root) return;linkNode(root, root->left);} private:/* * prev : 第h-1層的第一個節點* cur : 第h層的第一個節點*/void linkNode(TreeLinkNode* prev, TreeLinkNode* cur){if(!cur) return;/* 記錄第h層的第一個節點，用于下次遞歸 */TreeLinkNode* root = cur;while(prev){/* 依次設置next指針 */cur->next = prev->right;cur = cur->next;/* 移動prev */prev = prev->next;if(!prev) break;/* 繼續設置next指針 */cur->next = prev->left;cur = cur->next;}linkNode(root, root->left);} };

當然本題的前提是給定的二叉樹是完全二叉樹，即所有的葉子節點都在同一層

---

Populating Next Right Pointers in Each Node II

原題鏈接Populating Next Right Pointers in Each Node II

本題要求和上面一樣，不同的是這里給定的二叉樹不一定是完全二叉樹

需要改動的地方只有遞歸時的while循環，在循環中，每次都需要找到第h-1層的下一個節點，然后找到第h層的下一個節點，因為下一個節點不一定是prev的子節點。不過也方便，判斷prev的左右子節點是否存在即可

代碼如下

/*** Definition for binary tree with next pointer.* struct TreeLinkNode {* int val;* TreeLinkNode *left, *right, *next;* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}* };*/ class Solution { public:void connect(TreeLinkNode *root) {if(!root) return;/* 因為可能不是完全二叉樹，所以下一層的第一個節點需要手動尋找 */if(root->left)linkNode(root, root->left);elselinkNode(root, root->right);} private:/* prev : 第h-1層第一個節點* cur : 第ｈ層第一個節點 */void linkNode(TreeLinkNode* prev, TreeLinkNode* cur){if(!cur) return;TreeLinkNode* root = cur;while(prev && cur){/* 尋找第h層的下一個節點 */TreeLinkNode* curNext = nullptr;while(prev && !curNext){/* 因為cur最差也是prev的左節點，所以先從右節點判斷 */if(prev->right && prev->right != cur){curNext = prev->right;}else{/* 不是右節點，prev后移，然后判斷左節點 */prev = prev->next;/* 如果左節點存在，則就是h層的下一個節點，如果不存在，繼續判斷右節點 */curNext = prev ? prev->left : curNext;}}/* 設置nex指針 */cur->next = curNext;cur = curNext;}/* 尋找第h+1層的第一個節點 */while(root && !root->left && !root->right)root = root->next;if(!root) return;if(root->left)linkNode(root, root->left);elselinkNode(root, root->right);} };

本題的難點是當二叉樹不是平衡二叉樹時，如果尋找下一個節點，需要根據prev的next指針遍歷，找到第一個存在且和cur不相等的節點作為cur的下一個節點

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----为二叉树增加next节点，指向同一层的下一个节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。