Populating Next Right Pointers in Each Node
题目大意
为二叉树的节点都添加一个next指针，指向跟它在同一高度的右边的节点，如果右边没有节点，就指向None。
解题思路
递归，容易看懂。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| # 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 root and root.left: # 如有root和左孩子
root.left.next = root.right # 左孩子指向右孩子
if root.next: # 如链表有右边，那么其右孩子指向右边节点左孩子
root.right.next = root.next.left
else:
root.right.next = None
self.connect(root.left)
self.connect(root.right)
|
Populating Next Right Pointers in Each Node II
题目大意
二叉树并不都是满二叉树
解题思路
还是递归，但是情况考虑清楚
参考：http://www.cnblogs.com/zuoyuan/p/3745369.html
代码
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
| class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
if root:
if root.left and root.right:
root.left.next = root.right
tmp = root.next
while tmp: # 直到右边有第一个左孩子或者右孩子，连上后就break
if tmp.left: root.right.next = tmp.left; break
if tmp.right: root.right.next = tmp.right; break
tmp = tmp.next
elif root.left:
tmp = root.next # 即使有null，下面不遍历而已，并不会报错
while tmp: # 用左孩子去连接
if tmp.left: root.left.next = tmp.left; break
if tmp.right: root.left.next = tmp.right; break
tmp = tmp.next
elif root.right:
tmp = root.next
while tmp: # 用右孩子去连接
if tmp.left: root.right.next = tmp.left; break
if tmp.right: root.right.next = tmp.right; break
tmp = tmp.next
# 必须先遍历右边子树
self.connect(root.right)
self.connect(root.left)
|
总结
两道题目都是链表和二叉树结合，其实不难。
也还有很多解法，这两个比较通俗易懂。