力扣面试150题--填充每个节点的下一个右侧节点指针 II

Day 45

题目描述

思路

初次做法：考虑到每一节点都要指向它右边的第一个节点，那么我们需要从根向下，最好每次提前处理根节点指向它右边的节点，那么符合这样的遍历方法，很容易i想到前序遍历，但是前序遍历是有问题的，我们考虑以下样例：

如果我们采取前序遍历，在遍历到第四层的0这个点时，需要指向右边第一个节点，也就是8，但是此时它的父亲节点指向9，但是9并没有指向1，原因在于，我们并没有遍历到右子树的9号节点，因此此时0的next会指向null。
所以我们考虑遍历顺序变为根右左，先处理右子树，这样处理的好处是，由于每个节点都是不断指向右边的节点，先处理右子树，就会先处理好右子树的next，不会出现以上情况。
具体做法如下：

1. 以下全是递归函数内容
2. 判断该节点是否为空，为空返回null，非空继续。
3. 如果该节点左孩子非空，判断该节点的右孩子是否为空，不为空就将该节点的左孩子next指向右孩子；为空，定义一个节点为该节点指向的next节点，判断next的左孩子和右孩子是否为空，为空就继续指向下一个next，直到为null，非空，就指向左孩子或者右孩子（优先左孩子），然后退出循环
4. 如果该节点右孩子非空。同上
5. 递归该节点的右孩子
6. 递归该孩子的左孩子

/*
// 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 lian(Node root){//采取根右左if(root==null){//为空就返回nullreturn null;}if(root.left!=null){//左孩子不为空if(root.right!=null){//右孩子不为空就指向它root.left.next=root.right;}else{//右孩子为空if(root.next==null){//该节点的next指向为空，说明右边没有节点了root.left.next=null;}else{//不为空Node x=root.next;//新节点指向该节点的nextwhile(x!=null){//循环if(x.left==null&&x.right==null){//说明该节点没有能指向的孩子，继续下一个x=x.next;continue;}if(x.left!=null){//优先指向左孩子root.left.next=x.left;break;}if(x.right!=null){//再指向右孩子root.left.next=x.right;break;}}}}}if(root.right!=null){//基本同上if(root.next==null){root.right.next=null;}else{Node y=root.next;while(y!=null){if(y.left==null&&y.right==null){y=y.next;continue;}if(y.left!=null){root.right.next=y.left;break;}if(y.right!=null){root.right.next=y.right;break;}}}}lian(root.right);lian(root.left);return root;}public Node connect(Node root) {if(root==null){return null;}root.next=null;Node res= lian(root);return res;}
}

题解做法：直接采取层序遍历（居然没想到）

class Solution {public Node connect(Node root) {if (root == null) {return null;}Queue<Node> queue = new ArrayDeque<Node>();queue.offer(root);while (!queue.isEmpty()) {int n = queue.size();Node last = null;for (int i = 1; i <= n; ++i) {Node f = queue.poll();if (f.left != null) {queue.offer(f.left);}if (f.right != null) {queue.offer(f.right);}if (i != 1) {last.next = f;}last = f;}}return root;}
}