0117.md

Populating Next Right Pointers in Each Node II

题目

Given a binary tree

struct Node { int val; Node *left; Node *right; Node *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.

Example 1:
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:
Input: root = []
Output: []

思路

题意：和1的区别就是给的二叉树不是完美的二叉树，所以结点的右边有可能是空的，而右边的右边可能不是空的，需要next指向右边的第一个非nil结点。
如果右边都没有，则最后一个节点指向nil。

层序遍历，队列使用container/list
需要加一个map标记每一层的最后一个节点。
当遍历完最后一层的最后一个结点时，队列中的最后一个元素就是最后一个结点。

代码

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */
func connect(root *Node) *Node {
	if root == nil {
		return root
	}
	q := list.New()
	lastNodeMap := make(map[*Node]bool, 0)
	q.PushBack(root)
	lastNodeMap[root] = true
	for q.Len() > 0 {
		elem := q.Front()
		val := elem.Value
		node := val.(*Node)
		q.Remove(elem)
		//fmt.Printf("CUR NODE: %+v", node.Val)
		if q.Len() > 0 && !lastNodeMap[node] {
			node.Next = q.Front().Value.(*Node)
		} else {
			node.Next = nil
		}
		if node.Left != nil {
			q.PushBack(node.Left)
		}
		if node.Right != nil {
			q.PushBack(node.Right)
		}
		if q.Len() > 0 && lastNodeMap[node] {
			lastNodeMap[q.Back().Value.(*Node)] = true
		}
	}
	return root
}