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,
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
[解题思路]
与上一题类似,唯一的不同是每次要先找到一个第一个有效的next链接节点,并且递归的时候要先处理右子树,再处理左子树。
[Code]
1: void connect(TreeLinkNode *root) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: if(root== NULL) return;
5: TreeLinkNode* p = root->next;
6: while(p!=NULL)
7: {
8: if(p->left!=NULL)
9: {
10: p = p->left;
11: break;
12: }
13: if(p->right!=NULL)
14: {
15: p = p->right;
16: break;
17: }
18: p = p->next;
19: }
20: if(root->right!= NULL)
21: {
22: root->right->next = p;
23: }
24: if(root->left !=NULL)
25: {
26: root->left->next = root->right? root->right:p;
27: }
28: connect(root->right);
29: connect(root->left);
30: }
[Note]
1. Line 6, while loop, not if
For example,
Level 1 1
/ \
Level 2 2 3
/ \ \
Level 3 4 5 6
/
Level 4 7
When processing Level 3, while loop is necessary for finding a valid next.
Update 03/09/2014 Add a non-recursion version
1: void connect(TreeLinkNode *root) {
2: TreeLinkNode* cur = root, *next = NULL;
3: while(cur!=NULL)
4: {
5: TreeLinkNode *p = cur, *k= NULL;
6: while(p!=NULL)
7: {
8: TreeLinkNode* sub = getLinkedLeftNode(p);
9: if(sub != NULL)
10: {
11: if(next == NULL)
12: {
13: next = sub;
14: k = sub;
15: }
16: else
17: k->next = sub;
18: while(k->next !=NULL) // ietrate to the tail
19: k = k->next;
20: }
21: p = p->next;
22: }
23: cur = next;
24: next = NULL;
25: }
26: }
27: TreeLinkNode* getLinkedLeftNode(TreeLinkNode * root)
28: {
29: if(root->left != NULL && root->right != NULL)
30: root->left->next = root->right;
31: if(root->left != NULL)
32: return root->left;
33: if(root->right != NULL)
34: return root->right;
35: return NULL;
36: }
No comments:
Post a Comment