117.填充每个节点的下一个右侧节点指针II
给定一个二叉树：
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。
与LC116的区别在于，这个二叉树可能不是完全二叉树
- BFS：使用队列进行BFS
/* // 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; //cur我们可以把它看做是每一层的链表 Node cur = root; while (cur != null) { //遍历当前层的时候，为了方便操作在下一 //层前面添加一个哑结点（注意这里是访问 //当前层的节点，然后把下一层的节点串起来） Node dummy = new Node(0); //pre表示访下一层节点的前一个节点 Node pre = dummy; //然后开始遍历当前层的链表 while (cur != null) { if (cur.left != null) { //如果当前节点的左子节点不为空，就让pre节点 //的next指向他，也就是把它串起来 pre.next = cur.left; //然后再更新pre pre = pre.next; } //同理参照左子树 if (cur.right != null) { pre.next = cur.right; pre = pre.next; } //继续访问这样行的下一个节点 cur = cur.next; } //把下一层串联成一个链表之后，让他赋值给cur， //后续继续循环，直到cur为空为止 cur = dummy.next; } return root; } }
迭代遍历
- 设置节点cur，遍历每一层的链表
- 设置节点pre，将下一层的节点串起来
- 时间复杂度：O(n)
- 空间复杂度：O(1)
/* // 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; //cur我们可以把它看做是每一层的链表 Node cur = root; while (cur != null) { //遍历当前层的时候，为了方便操作在下一 //层前面添加一个哑结点（注意这里是访问 //当前层的节点，然后把下一层的节点串起来） Node dummy = new Node(0); //pre表示访下一层节点的前一个节点 Node pre = dummy; //然后开始遍历当前层的链表 while (cur != null) { if (cur.left != null) { //如果当前节点的左子节点不为空，就让pre节点 //的next指向他，也就是把它串起来 pre.next = cur.left; //然后再更新pre pre = pre.next; } //同理参照左子树 if (cur.right != null) { pre.next = cur.right; pre = pre.next; } //继续访问这样行的下一个节点 cur = cur.next; } //把下一层串联成一个链表之后，让他赋值给cur， //后续继续循环，直到cur为空为止 cur = dummy.next; } return root; } }
