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). For example, Given the following perfect binary tree,
1 / / 2 3 / / / /4 5 6 7After calling your function, the tree should look like:
1 -> NULL / / 2 -> 3 -> NULL / / / /4->5->6->7 -> NULL解法一，使用隊列，時間復雜度O(N）：
/** * 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 == NULL) return ; std::queue<TreeLinkNode*> que; que.push(root); while(!que.empty()){ const int size = que.size(); for(int i=0; i<size; ++i){ TreeLinkNode* tmp = que.front(); que.pop(); if(!que.empty() && i != size-1) tmp->next = que.front(); //default tmp1->next = NULL; if(tmp->left != NULL) que.push(tmp->left); if(tmp->right != NULL) que.push(tmp->right); } } }};解法二，遞歸：
class Solution {public: void connect(TreeLinkNode *root) { if(root == NULL) return ; if(root->left != NULL){ root->left->next = root->right; //perfect binary tree if(root->next != NULL) root->right->next = root->next->left; } connect(root->left); connect(root->right); }};這道題一開始我使用遞歸，我一直想借助后續遍歷的思路。事實證明，不要死搬硬套！要針對實際情況遞歸。
新聞熱點
疑難解答
