友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

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

给定一个二叉树:

struct Node {
  int val;
  Node left;
  Node right;
  Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL

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

示例 1:

0117 1
输入: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

进阶:

  • 你只能使用常量级额外空间。

  • 使用递归解题也符合要求,本题中递归程序的隐式栈空间不计入额外空间复杂度。

思路分析

这道题和 116. Populating Next Right Pointers in Each Node 算是姊妹题。

最简单的方式,使用 Deque 来保存每一层节点,然后建立起来"连接"。但是,很明显,这种方案不符合空间复杂度要求。

基于上面这种解法,再深入思考一步,上面使用 Deque 就是想要保存接下来需要访问的元素,并且保存访问的前后顺序。现在 Node 上有 next 字段,可以利用这个字段,打通这条链表,遍历上一层时,打通下一次的链接结构。这里需要保存的就有两点:

  1. 这条链表的头结点,用于下一层的遍历;

  2. 这条链表的尾节点,用于添加下一个节点。

这道题的思路和 116. Populating Next Right Pointers in Each Node 思路几乎是一样的:在上层遍历中,建立下一层的链接。

但这道题和 116. Populating Next Right Pointers in Each Node 在于:116 是完全二叉树,那么可以直接使用 next 节点的 left 子节点。这道题不是一个完全二叉树,所以,就需要在运动中寻找不为空的节点。另外,最左节点的选择,也不能直接使用 mostLeft.left,也是需要在运动中去寻找下一层第一个不为空的节点。两道题区别不大只是需要多注意细节。

0117 2

这样,把第一种解法的代码稍作修改就可以了。

看题解,别人大部分是用了两层循环,外层是负责向下推进,内层负责同层向右。D瓜哥用了一层循环来遍历每个节点。

  • 一刷

  • 二刷

  • 二刷(优化)

  • 三刷

 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-02-09 23:17
 */
static class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node(int x) {
        this.val = x;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}


/**
 * Runtime: 1 ms, faster than 49.14% of Java online submissions for Populating Next Right Pointers in Each Node II.
 * Memory Usage: 41.4 MB, less than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node II.
 *
 * Copy from: https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-28/[详细通俗的思路分析,多解法 - 填充每个节点的下一个右侧节点指针 II - 力扣(LeetCode)]
 */
public Node connect(Node root) {
    Node curr = root;
    while (Objects.nonNull(curr)) {
        Node dummy = new Node(0);
        Node tail = dummy;
        while (Objects.nonNull(curr)) {
            if (Objects.nonNull(curr.left)) {
                tail.next = curr.left;
                tail = tail.next;
            }
            if (Objects.nonNull(curr.right)) {
                tail.next = curr.right;
                tail = tail.next;
            }
            curr = curr.next;
        }
        curr = dummy.next;
    }
    return root;
}

/**
 * Runtime: 1 ms, faster than 49.14% of Java online submissions for Populating Next Right Pointers in Each Node II.
 * Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node II.
 */
public Node connectDeque(Node root) {
    if (Objects.isNull(root)) {
        return null;
    }
    Deque<Node> deque = new LinkedList<>();
    deque.addLast(root);
    Node prev = null;
    while (!deque.isEmpty()) {
        int size = deque.size();
        for (int i = 0; i < size; i++) {
            Node curr = deque.removeFirst();
            if (Objects.nonNull(curr.left)) {
                deque.addLast(curr.left);
            }
            if (Objects.nonNull(curr.right)) {
                deque.addLast(curr.right);
            }
            if (i > 0) {
                prev.next = curr;
            }
            prev = curr;
        }
    }
    return root;
}
 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
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-25 17:26:18
 */
public Node connect(Node root) {
  if (root == null) {
    return null;
  }
  Queue<Node> queue = new LinkedList<>();
  queue.offer(root);
  while (!queue.isEmpty()) {
    int size = queue.size();
    Node pre = null;
    for (int i = 0; i < size; i++) {
      Node cur = queue.poll();
      if (pre != null) {
        pre.next = cur;
      }
      if (cur.left != null) {
        queue.offer(cur.left);
      }
      if (cur.right != null) {
        queue.offer(cur.right);
      }
      pre = cur;
    }
  }
  return root;
}
 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
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-25 17:26:18
 */
public Node connect(Node root) {
  if (root == null) {
    return null;
  }
  Node mostLeft = root;
  while (mostLeft != null) {
    Node cur = mostLeft;
    mostLeft = null;
    Node prev = null;
    while (cur != null) {
      if (cur.left != null) {
        // 不能保证左子树的最节点就一定有值
        // 所以,在运动中,寻找最左节点
        if (mostLeft == null) {
          mostLeft = cur.left;
        }
        // 由于不是完全二叉树,
        // 所以需要在运动中寻找不为空的节点
        if (prev != null) {
          prev.next = cur.left;
          prev = prev.next;
        } else {
          prev = cur.left;
        }
      }
      if (cur.right != null) {
        // 不能保证左子树的最节点就一定有值
        // 所以,在运动中,寻找最左节点
        if (mostLeft == null) {
          mostLeft = cur.right;
        }
        // 由于不是完全二叉树,
        // 所以需要在运动中寻找不为空的节点
        if (prev != null) {
          prev.next = cur.right;
          prev = prev.next;
        } else {
          prev = cur.right;
        }
      }
      cur = cur.next;
    }
  }
  return root;
}
 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
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-06-04 21:38:37
 */
public Node connect(Node root) {
  if (root == null) {
    return root;
  }
  Node cur = root;
  Node mostLeft = root;
  Node prev = null;
  while (cur != null) {
    // 寻找下一层最左节点
    if (cur == mostLeft || mostLeft == null) {
      mostLeft = cur.left;
      if (mostLeft == null) {
        mostLeft = cur.right;
      }
    }
    if (prev != null) {
      if (cur.left != null) {
        prev.next = cur.left;
        prev = prev.next;
      }
      if (cur.right != null) {
        prev.next = cur.right;
        prev = prev.next;
      }
    } else {
      if (cur.left != null) {
        prev = cur.left;
      }
      if (cur.right != null) {
        if (prev != null) {
          prev.next = cur.right;
          prev = prev.next;
        } else {
          prev = cur.right;
        }
      }
    }
    if (cur.next != null) {
      cur = cur.next;
    } else {
      cur = mostLeft;
      prev = null;
    }
  }
  return root;
}