# int32bit / leetcode

Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
tree.cpp

## Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example, Given the following binary tree,

``````         1
/  \
2    3
/ \    \
4   5    7
``````

After calling your function, the tree should look like:

``````         1 -> NULL
/  \
2 -> 3 -> NULL
/ \    \
4-> 5 -> 7 -> NULL
``````

## Solution

``````     p  ->   q
\
r2
\
r22

getNext(p) == r2， 此时p == q， 因为原来的p没有孩子
getNext(q) == r2, 此时q不变，q有孩子
getNext(r2) == r22，r2不变，r2有孩子

``````

```TreeLinkNode *getNext(TreeLinkNode * &p) {
if (p == nullptr)
return nullptr;
TreeLinkNode *next = p->left ? p->left : p->right;
if (next)
return next;
p = p->next;
return getNext(p);
}```

``````     p  ->   q
/         \
l1         r2
/  \       /  \
l11  l12   r21  r22
``````

``````     p  ->   q
/         \
l1   ->    r2
/  \       /  \
l11  l12   r21  r22
``````

```void connect(TreeLinkNode *root) {
if (root == nullptr)
return;
TreeLinkNode *p = root;
while (p) {
TreeLinkNode *q = p;
TreeLinkNode *t1 = getNext(q);
while (t1) {
if (t1 == q->left) { // 如果t1是左孩子
t2 = q->right; // 令t2是它的右孩子，（可能为null）
} else {
t2 = nullptr; // 否则t1已经是右孩子，t2必须从下一个节点寻找
}
if (t2 == nullptr) {
q = q->next; // 从下一个节点寻找t2
t2 = getNext(q);
}
if (t2 == nullptr) // t2为null，说明没有找到最右相邻节点
break;
t1->next = t2; // 更新t1的next指针指向t2
t1 = t2;
}
p = getNext(p); // 处理下一层节点，注意下一层的最初节点就是p的下一层节点的最左节点，即getNext(p)
}
}```

## 扩展

Populating Next Right Pointers in Each Node

## 总结

```public void connect(TreeLinkNode root) {
while(root != null){