Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL
.
Initially, all next pointers are set to NULL
.
Note:
- You may only use constant extra space.
- You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
'''
Created on Nov 19, 2014 @author: ScottGu<gu.kai.66@gmail.com, 150316990@qq.com>
'''
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None class Solution:
# @param root, a tree node
# @return nothing
def connect(self, root):
stack=[]
if(root==None): return
stack.append(root)
while(len(stack)!=0):
for ix in range(len(stack)-1):
stack[ix].next=stack[ix+1]
stack[-1].next=None
cntOfLastLevel=len(stack)
for ix in range(cntOfLastLevel):
if (stack[0].left!=None):stack.append(stack[0].left)
if (stack[0].right!=None):stack.append(stack[0].right)
stack.remove(stack[0]) class Solution2:
# @param root, a tree node
# @return nothing
def connect(self, root):
if(root==None): return
head_high=cursor_high=root
head_low = cursor_low=None while(cursor_high.left!=None):
head_low = cursor_low=cursor_high.left cursor_low.next=cursor_high.right
cursor_low=cursor_low.next
while(cursor_high.next!=None):
cursor_high=cursor_high.next
cursor_low.next=cursor_high.left
cursor_low=cursor_low.next
cursor_low.next=cursor_high.right
cursor_low=cursor_low.next
cursor_low.next=None head_high=cursor_high=head_low
题目和代码如上所述,这个题比较有意思的地方是,这个数据结构有点像数据库索引的结构,上述代码实现了两种方法,两种方法都是层级遍历,时间复杂度都是O(N),但空间复杂度不一样,实现难度也不一样。
1. 第一种更为简单,但使用了额外的空间用于存储上一层节点,最大空间复杂度为所有叶子节点的大小之和。所以类似这种算法如果用于建立DB索引的话,恐怕内存就要爆掉了,第二种方法则没有问题。
2. 第二种稍复杂,但是空间复杂度只有O(1),也就是无需任何额外内存。实现方法是使用两个游标和1个标志位,两个游标用于并行遍历两行nodes,1个标志位用于标记下面那行的head。
两游标并行往前走,会同时走到各自行的结尾,这时两游标各自下移到下一行开始(这就是为啥要标记那行的head)然后重复上面的过程继续往前走,当没有下一行时停止(第二个游标没得指了),请自行脑补2个游标遍历所有nodes并且加链接的过程。