117. Populating Next Right Pointers in Each Node II
C++。应该是更新测点了，使得时间变长了。。。
讲一下思路。
dfs，深搜，和上一题的区别是这不是完全二叉树了，所以要注意几个点：
- 可能有右子树，但没有左子树；
- 要用node->next指向堂兄弟时，可能堂兄弟不是左子结点，而可能是右子结点；
- 需要先找到右边的堂兄弟结点，所以注意两点：
- 先遍历右子树；
- 右边堂兄弟可能不存在。。。
代码如下：
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() {}
Node(int _val, Node* _left, Node* _right, Node* _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if (!root) return NULL;
Node *next = root->next;
while (next) {
if (next->left) {
next = next->left;
break;
} else if (next->right) {
next = next->right;
break;
} else next = next->next;
}
if (root->left && root->right) {
root->left->next = root->right;
root->right->next = next;;
} else if (!root->left && root->right) root->right->next = next;
else if (root->left && !root->right) root->left->next = next;
connect(root->right);
connect(root->left);
return root;
}
};
