Populating Next Right Pointers in Each Node II
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
思路
root的左右节点的next指向分别在哪里？next指向。
递归 是先递归右节点 然后再左结点
解题
c++版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
32
33
34
35
36
37/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
if(!root)
return;
TreeLinkNode *rootNext=root->next;
TreeLinkNode *next=NULL;
while(rootNext!=NULL && next==NULL){
if(rootNext->left!=NULL){
next=rootNext->left;
}
else{
next=rootNext->right;
}
rootNext=rootNext->next;
}
if(root->left!=NULL){
if(root->right!=NULL)
root->left->next=root->right;
else
root->left->next=next;
}
if(root->right!= NULL){
root->right->next = next;
}
connect(root->right);
connect(root->left);
}
};
python版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# Definition for binary tree with next pointer.
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
if not root:
return
rootNext=root.next
next1=None
while rootNext!=None and next1==None:
if(rootNext.left):
next1=rootNext.left
else:
next1=rootNext.right
rootNext=rootNext.next
if(root.left):
if(root.right):
root.left.next=root.right
else:
root.left.next=next1
if root.right:
root.right.next=next1
self.connect(root.right)
self.connect(root.left)
