题目描述:给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
1 2 3 4 5 6
| class Node { int val; Node left; Node right; Node next; }
|
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。初始状态下,所有 next 指针都被设置为 NULL。你只能使用常量级额外空间。使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public Node connect(Node root) { if (root == null || (root.left == null && root.right == null)) { return root; }
Node leftNode = connect(root.left);
Node rightNode = connect(root.right);
while (leftNode != null){ leftNode.next = rightNode; leftNode = leftNode.right; rightNode = rightNode.left; } return root; } }
|