Question:
Given a binary tree
struct Node {
Node* leftChild;
Node* rightChild;
Node* nextRight;
}
Populate the nextRight pointers in each node.
The first idea come out should be the BFS tree algorithm, which can traverse the binary tree layer by layer. We only need to connect the sibling for each layer.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
<pre>intpopulateNextRightBFS(Node* root) { if(!root) return0; queue <Node*> q; q.push(root); intnextLayer = 0; intcurLayer = 1; Node* prev = NULL; while(!queue.empty()) { Node* cur = queue.front(); if(prev) prev->sibling = cur; if(cur->left) { queue.push(cur->left); nextLayer++; } if(cur->right) { queue.push(cur->right); nextLayer++; } queue.pop(); curLayer--; prev = cur; if(!curLayer) { curLayer = nextLayer; nextLayer = 0; prev = NULL; } } return0;} |
Above algorithm uses an queue, which can be saved actually. We could use the parent’s sibling to visit children’ siblings. Then we have the following algorithm.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
<pre>intpopulateNextRightExt(Node* root) { if(!root) return0; if(root->left) root->left->sibling= root->right; Node* cur = root; if(root->right) { while(cur->sibling && !cur->sibling->left && !cur->sibling->right) cur = cur->sibling; if(cur->sibling && cur->sibling->left) root->right->sibling = cur->sibling->left; elseif root->right->sibling = cur->sibling->left; else root->right->sibling = NULL; } populateNextRight(root->right); populateNextRight(root->left); return0;} |
P.S If the sibling only points to the node in one-step right, and NULL otherwise, we do not need to search for its sibling far away. The simplified algorithm is as follows.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
<pre>intpopulateNextRight(Node* root) { if(!root) return0; if(root->left) root->left->sibling= root->right; if(root->right) root->right->sibling = (root->sibling) ? root->sibling->left : NULL; populateNextRight(root->right); populateNextRight(root->left); return0;} |