LeetCode日记— 117. Populating Next Right Pointers in Each Node II

发布于 2020-09-28  110 次阅读


碎碎念:没啥好碎碎念的今天,不过感觉又要刷leetcode又要学雅思,也挺累的呢。。

题目如下:

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

You may only use constant extra space.
Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.
 

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

思路:

本题的本质就是遍历每一层,然后将其连起来。既然如此我们很快就想到了BFS,因为BFS就是从上往下按层遍历的。但是真的只是普通的BFS就可以了吗?也不是这样的,一般来说BFS都是将某个节点的左右孩子放入队列(或者其他数据结构)中达到广度优先搜索的目的。但是BFS的时候我们并不能知道何时到了下面一层。

为了解决这个办法,我们可以在x-1层的时候进行一些操作,这时节点的左右孩子就都是x层的了。但是我们又如何知道哪些节点是x-1层的呢?我们可以设置一个从左到右的队列,放入每一层的所有节点。

代码如下:


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

但是题目已经要求了要O(1)的空间复杂度,那么如果我们再用栈来存某一层的节点就无法达到要求了。我们的队列就是为了把同一层的节点存起来,那么如果我们在x-1层就用操作把x层按照顺序连起来了,不就可以了吗?

代码如下:

class Solution {
    Node last = null, nextStart = null;

    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Node start = root;
        while (start != null) {
            last = null;
            nextStart = null;
            for (Node p = start; p != null; p = p.next) {
                if (p.left != null) {
                    handle(p.left);
                }
                if (p.right != null) {
                    handle(p.right);
                }
            }
            start = nextStart;
        }
        return root;
    }

    public void handle(Node p) {
        if (last != null) {
            last.next = p;
        } 
        if (nextStart == null) {
            nextStart = p;
        }
        last = p;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-15/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

其实我一开始有想过这种方法的,但是苦于不知道如何得到x-1层有哪些节点。上面的是官方代码,官方代码中使用了一个for循环,在循环里布尔表达式是当前遍历的节点是否为空,之后每次向后移动一位当前指针(x-2层的操作已经把x-1层连起来了)。这样这一层的结束判定就很明显了。一般来说for中的stepping都是用++或者- -来计数,一下子没想到往后面移动的stepping方式,果然还是我太彩笔了。

PS:记一个小知识点,我一直以为for循环判断完布尔表达式以后就会执行for循环的第三项,也就是stepping的操作,但是查了一下thinking in java才知道是每次循环结束以后才进行操作的。


你好哇!欢迎来到雷公马碎碎念的地方:)