LeetCode117.填充每个节点的下一个右侧节点指针 II

发表于 更新于 分类于 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 3 分钟

LeetCode117.填充每个节点的下一个右侧节点指针 II【medium】。

题目描述

给定一个二叉树:

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。

输入输出示例

示例 1：
117示例
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），’#’ 表示每层的末尾。

示例 2：
输入：root = []
输出：[]

提示：

  • 树中的节点数在范围 [0, 6000] 内
  • -100 <= Node.val <= 100

题目分析

方法一：层序遍历

由图示可知，每一个节点的 next 指的就是和节点处于同一层的下一个节点，我们很容易想到二叉树的层序遍历。二叉树常规的层序遍历方式是使用一个 Queue，首先把二叉树的根节点入队，然后当队列数目不为空时，将队头元素出队，然后将出队元素的左右孩子入队（如果存在的话），直到 Queue 数目为0结束循环。
但依照题意，我们想要的是将某一层的节点全部相连，而普通层序遍历时，Queue 中的元素某一时刻并不一定是同一层的，所以我们可以在层序遍历的基础上稍微进行一些修改，找到属于同一层的所有节点。具体的方式就是在一次 while 循环开启的时候，记录下当前 Queue 中的数目元素 n，然后通过 for 循环进行 n 次出队操作，这样就能保证每一次循环出队列的元素都是同一层的，while 结束后的 Queue 元素都是下一层的。

方法二：使用已建立的 next 指针

方法一使用了层序遍历，需要额外的空间。由于必须遍历所有节点，所以无法降低时间复杂度，但可以考虑如何降低空间复杂度。我们由题意可以知道，当我们遍历某一层节点时，由于我们已知每一个节点的 left 和 right，所以其实对于下一层的构造，我们也可以确定。对于每一层，只要知道最左边的节点，就可以遍历该层了。所以从根节点开始，我们可以建立下一层的 next，然后遍历下一层，再建立下下层的 next，以此类推，就不需要使用额外空间了。

题解

题解一：层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
// Definition for a Node.
public 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;
    }
}
*/

public class Solution {
    public Node Connect(Node root) {
        if(root == null) {
            return null;
        }
        Queue<Node> queue = new Queue<Node>();
        Node last = null; //last代表上一次访问的节点
        queue.Enqueue(root);
        while(queue.Count > 0) {
            last = null; //每一层和上一层无需串联，对于每一层的循环，需要把last置空
            int n = queue.Count; //n不能在循环里获取，因为count数目会发生变化
            for(int i = 1; i <= n; i++) {
                Node temp = queue.Dequeue();
                if(temp.left != null) {
                    queue.Enqueue(temp.left);
                }
                if(temp.right != null) {
                    queue.Enqueue(temp.right);
                }
                //如果当前节点不是首节点，那么就将当前节点作为上一次节点的next
                if(i != 1) {
                    last.next = temp;
                }
                last = temp; //更新last节点
            }
        }
        return root;
    }
}

题解二：使用已建立的 next 指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
// Definition for a Node.
public 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;
    }
}
*/

public class Solution {
    Node last = null, nextStart = null; //last代表上一次访问的节点，nextStart代表下一层开始的节点
    public Node Connect(Node root) {
        if(root == null) {
            return null;
        }
        Node start = root; //start代表本层开始的节点
        while(start != null) {
            Node temp = start; //temp代表当前遍历到的节点
            last = null; // 对于每次循环，都要置空last和nextStart
            nextStart = null;
            while(temp != null) {
                //根据当前节点的left和right建立next连接
                if(temp.left != null) {
                    Handle(temp.left);
                }
                if(temp.right != null) {
                    Handle(temp.right);
                }
                temp = temp.next; //更新temp节点
            }
            start = nextStart; //遍历完当前层后更新start
        }
        return root;
    }

    void Handle(Node p) {
        // 上一次节点不为空，说明本层有前边的节点，将p设为last的next
        if(last != null) {
            last.next = p;
        }
        //nextstart为空，说明某次循环刚开始，p是某一层的首节点
        if(nextStart == null) {
            nextStart = p;
        }
        last = p; //更新last
    }
}