原题
给定一个二叉树
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
说明:
你只能使用额外常数空间。
使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例:
给定二叉树,
1 / \ 2 3 / \ \ 4 5 7
调用你的函数后,该二叉树变为:
1 -> NULL / \ 2 -> 3 -> NULL / \ \ 4->5-> 7-> NULL
思路
此题是 LeetCode 116 填充同一层的兄弟节点 的改版, 不同点在于输入的树不再是完美二叉树。其实思路和116题相同,把问题转化为给定一层已经链接的节点,请链接下面一层。由于不再是完美二叉树,首个节点需要另外记录。因此给需要链接的层建立一个哨兵节点,依次链接该层节点。之后,递归传入该层的第一个节点,即dummy.next。
代码
# 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
cur = root
dummy = p = TreeLinkNode(0)
while cur:
if cur.left:
p.next = cur.left
p = p.next
if cur.right:
p.next = cur.right
p = p.next
cur = cur.next
self.connect(dummy.next)