leetcode 116. 填充每个节点的下一个右侧节点指针

leetcode 116. 填充每个节点的下一个右侧节点指针

题目

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

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

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

思路

这道题假设用层序遍历开一个队列来做其实非常的简单，但是他既然说了进阶要不开额外空间，这一点就值得考量了。实际上就是怎样才能去掉这个队列呢，那就必然得拿到下一个节点，这个可以借助父节点的next来做，因为遍历到下一层的时候，父节点的next是已知的。所以就一目了然了，这道题除了迭代外，还可以用递归。

代码

// 迭代
/*
// 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;}// Deque<Node> queue = new ArrayDeque<Node>();// queue.offerLast(root);Node node = root;while (node.left != null) {Node firstnode = node;while (node != null) {if (node.left != null) {node.left.next = node.right;}if (node.next != null) {node.right.next = node.next.left;}node = node.next;}node = firstnode.left;}return root;}
}
// 递归
/*
// 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 null;}if (root.left != null) {root.left.next = root.right;root.right.next = root.next == null ? null : root.next.left;connect(root.left);connect(root.right);}return root;}
}