题目描述

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

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

 

示例：

输入：{“$id”:”1″,”left”:{“$id”:”2″,”left”:{“$id”:”3″,”left”:null,”next”:null,”right”:null,”val”:4},”next”:null,”right”:{“$id”:”4″,”left”:null,”next”:null,”right”:null,”val”:5},”val”:2},”next”:null,”right”:{“$id”:”5″,”left”:{“$id”:”6″,”left”:null,”next”:null,”right”:null,”val”:6},”next”:null,”right”:{“$id”:”7″,”left”:null,”next”:null,”right”:null,”val”:7},”val”:3},”val”:1}

输出：{“$id”:”1″,”left”:{“$id”:”2″,”left”:{“$id”:”3″,”left”:null,”next”:{“$id”:”4″,”left”:null,”next”:{“$id”:”5″,”left”:null,”next”:{“$id”:”6″,”left”:null,”next”:null,”right”:null,”val”:7},”right”:null,”val”:6},”right”:null,”val”:5},”right”:null,”val”:4},”next”:{“$id”:”7″,”left”:{“$ref”:”5″},”next”:null,”right”:{“$ref”:”6″},”val”:3},”right”:{“$ref”:”4″},”val”:2},”next”:null,”right”:{“$ref”:”7″},”val”:1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

题目地址
中文版
英文版

代码实现

class Solution(object):
	def connect(self, root):
		"""
		:type root: Node
		:rtype: Node
		"""
		if(not root):
			return root
		queue = [root]
		while queue:
			size = len(queue)
			pre = queue[0]
			for i in xrange(1,size):
				pre.next = queue[i]
				pre = queue[i]
			for _ in xrange(size):
				node = queue.pop(0)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return root
                                                                    

4 次阅读