Leetcode 117. Populating Next Right Pointers in Each Node II | | Leetcode 117. Populating Next Right Pointers in Each Node II 文章作者:Tyan博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Version 1 12345678910111213141516171819202122232425262728293031323334353637383940/** * 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; } queue<TreeLinkNode*> q1; q1.push(root); queue<TreeLinkNode*> q2; TreeLinkNode* pre = nullptr; TreeLinkNode* current = nullptr; while(!q1.empty()) { current = q1.front(); q1.pop(); if(current->left) { q2.push(current->left); } if(current->right) { q2.push(current->right); } if(pre) { pre->next = current; } pre = current; if(q1.empty()) { q1 = q2; q2 = {}; pre = nullptr; } } }}; Version 2 12345678910111213141516171819202122232425262728293031323334353637383940414243/** * 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; } queue<TreeLinkNode*> q; q.push(root); connect(q); }private: void connect(queue<TreeLinkNode*>& q) { TreeLinkNode* pre = nullptr; TreeLinkNode* current = nullptr; queue<TreeLinkNode*> q2; while(!q.empty()) { current = q.front(); q.pop(); if(current->left) { q2.push(current->left); } if(current->right) { q2.push(current->right); } if(pre) { pre->next = current; } pre = current; } if(!q2.empty()) { connect(q2); } }}; Version 3 1234567891011121314151617181920212223242526272829303132333435363738394041/** * 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; } TreeLinkNode* parent = root; TreeLinkNode* head = new TreeLinkNode(0); while(root) { parent = root; TreeLinkNode* current = head; while(parent) { if(parent->left && parent->right) { current->next = parent->left; current->next->next = parent->right; current = parent->right; } else if(parent->left) { current->next = parent->left; current = parent->left; } else if(parent->right){ current->next = parent->right; current = parent->right; } parent = parent->next; } current->next = nullptr; root = head->next; } delete head; }}; Reference https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/ 如果有收获,可以请我喝杯咖啡! 赏 微信打赏 支付宝打赏