0%

leetCode-116:Populating Next Right Pointers in Each Node

问题描述

给定一个完全二叉树,要求填充每个节点的下一个节点(指向节点右边的兄弟节点,没有右边的节点则填充为空)。题目链接:**点我**

样例输入输出

输入:[1,2,3,4,5,6,7]

代表这是一个三层的二叉树,从上到下,从左到右的节点是:1,2,3,4,5,6,7。其中 1 的左孩子是 2,右孩子是 3,依次类推

输出:[1,#,2,3,#,4,5,6,7,#]

这是补充上节点右边节点后,按照从上到下,从左到右的节点的遍历的输出结果,其中 # 代表空

输入:[1]

输出:[1]

问题解法

按照先序遍历树的方式遍历每个节点,在每个节点上,将左孩子的 next 指针指向右孩子,将右孩子的 next 指针指向当前节点的 next 节点的左孩子(如果存在的话,不存在就是 null)。代码如下

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;

public Node() {}

public Node(int _val) {
val = _val;
}

public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution
{
public Node connect(Node root)
{
if (root == null)
{
return root;
}

if (root.left != null)
{
root.left.next = root.right;
}

if (root.next != null && root.right != null)
{
root.right.next = root.next.left;
}

connect(root.left);
connect(root.right);

return root;
}
}