题目描述

给定一个二叉树

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

说明:

你只能使用额外常数空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两个子节点）。

示例:

给定完美二叉树，

调用你的函数后，该完美二叉树变为：

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

我的解法——递归（AC）

递归：
- 这道题的特别之处在于不仅仅要遍历树，并且要找到每一层的最右节点，使其指向null。并且需要常数级别的额外空间，因此遍历树应该选用递归而非循环。
- 借用 next 指针，做到不需要队列就能完成广度优先搜索（BFS）：如果当前层所有结点的 next 指针已经设置好了，那么据此，下一层所有结点的 next 指针也可以依次被设置。
- 由于是完全二叉树，所以若节点的左子结点存在的话，其右子节点必定存在，所以左子结点的next指针可以直接指向其右子节点，对于其右子节点的处理方法是，判断其父节点的next是否为空，若不为空，则指向其next指针指向的节点的左子结点，若为空则指向NULL。
时间复杂度O(n)，空间复杂度O(1)
Beat 92%

# 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):
            if(root.left):
                root.left.next = root.right
            if(root.next and root.right):
                root.right.next = root.next.left
            self.connect(root.left)
            self.connect(root.right)