导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-116.Populating Next Right Pointers in Each Node

题目

Given a binary tree

1
2
3
4
5
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

翻译

给出二叉树

1
2
3
4
5
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}

令每个节点的next指向其右边的节点。如果其右边没有节点,那么next应当设为NULL。
所有next指针都被初始化为NULL。
注意:
你只可以使用常数额外空间。
你可以认为这是一颗完全二叉树(即所有的叶子节点都在同一层,并且每个父节点都有两个孩子节点)。
例如,给出如下完全二叉树,
     1
    / \
   2   3
  / \  / \
 4  5 6  7
在调用你的函数之后,树应当变成:
     1 -> NULL
    /  \
   2 ->  3 -> NULL
  / \   / \
 4-> 5-> 6-> 7 -> NULL

本题的难点在于只能使用常数额外空间,所以不能广度遍历。
注意到题中的next指针可以复用,有:
node.left.next = node.right
node.right.next = node.next.left
从root开始,设立first指向下一行的第一个节点,node临时节点从第一个节点开始,利用next指针在本层逐渐向后遍历,遍历过程中将下一层的next指针指好。
当first的下一层指针为空时,表示已经到最下层,退出循环:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return;
TreeLinkNode first = root;
while (first.left != null) {
TreeLinkNode node = first;
first = first.left;
while (node != null) {
node.left.next = node.right;
node.right.next = node.next == null ? null : node.next.left;
node = node.next;
}
}
}
}

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for binary tree with next pointer.
# class TreeLinkNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None

class Solution(object):
def connect(self, root):
"""
:type root: TreeLinkNode
:rtype: nothing
"""
if not root:
return
next_level_first_Node = root
while next_level_first_Node.left:
node = next_level_first_Node
next_level_first_Node = next_level_first_Node.left
while node:
node.left.next = node.right
if node.next:
node.right.next = node.next.left
node = node.next

另附广度优先遍历版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return;
Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
TreeLinkNode node = root;
queue.add(node);
while (!queue.isEmpty()) {
int size = queue.size();
TreeLinkNode cur = null, next = null;
while (size-- > 0) {
cur = queue.poll();
next = size == 0 ? null : queue.peek();
cur.next = next;
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
}
}
}
}

参考:
http://www.cnblogs.com/felixfang/p/3647898.html