Populating Next Right Pointers in Each Node

题目大意

为二叉树的节点都添加一个next指针，指向跟它在同一高度的右边的节点，如果右边没有节点，就指向None。

解题思路

递归，容易看懂。

代码

# 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

代码

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)

总结

两道题目都是链表和二叉树结合，其实不难。
也还有很多解法，这两个比较通俗易懂。