首先是自己写的迭代,用的是队列的数据结构,贴代码
1 /* 2 // Definition for a Node. 3 class Node { 4 public: 5 int val; 6 Node* left; 7 Node* right; 8 Node* next; 9 10 Node() : val(0), left(NULL), right(NULL), next(NULL) {} 11 12 Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} 13 14 Node(int _val, Node* _left, Node* _right, Node* _next) 15 : val(_val), left(_left), right(_right), next(_next) {} 16 }; 17 */ 18 19 class Solution { 20 public: 21 Node* connect(Node* root) 22 { 23 if(!root) 24 return NULL; 25 int i = 1; 26 queue<Node*> Node_que; 27 Node_que.push(root); 28 while(!Node_que.empty()) 29 { 30 for(int j = 0 ; j < i ; j++) 31 { 32 Node* temp = Node_que.front(); 33 if(temp->left) 34 { 35 Node_que.push(temp->left); 36 Node_que.push(temp->right); 37 } 38 Node_que.pop(); 39 if(j != i-1) 40 { 41 temp->next = Node_que.front(); 42 } 43 } 44 i = i*2; 45 } 46 return root; 47 } 48 };
递归写不出来,还有一种迭代的思路,通过上一层实现的next指针,来实现下一层的相连,相同父节点之间的链接好办,主要是不同父节点之间的连接较难处理,在上一层有next指针的情况下,就能够有效的完成
1 /* 2 // Definition for a Node. 3 class Node { 4 public: 5 int val; 6 Node* left; 7 Node* right; 8 Node* next; 9 10 Node() : val(0), left(NULL), right(NULL), next(NULL) {} 11 12 Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} 13 14 Node(int _val, Node* _left, Node* _right, Node* _next) 15 : val(_val), left(_left), right(_right), next(_next) {} 16 }; 17 */ 18 19 class Solution { 20 public: 21 Node* connect(Node* root) 22 { 23 if(!root) 24 return root; 25 Node* Left_most = root; 26 while(Left_most->left) 27 { 28 Node* node = Left_most; 29 while(node) 30 { 31 node->left->next = node->right; 32 if(node->next) 33 { 34 node->right->next = node->next->left; 35 } 36 node = node->next; 37 } 38 Left_most = Left_most->left; 39 } 40 return root; 41 } 42 };