关注Java领域相关技术 记录有趣的事情

LeetCode-116. 填充每个节点的下一个右侧节点指针

US-B.Ralph
US-B.Ralph
2020-10-15

问题地址

LeetCode每日一题/2020-10-15

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

问题描述

规则

  • 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
  • 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
  • 初始状态下，所有 next 指针都被设置为 NULL。

进阶

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例

  • 示例1
输入：{"id":"1","left":{"id":"2","left":{"id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"id":"5","left":{"id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出：{"id":"1","left":{"id":"2","left":{"id":"3","left":null,"next":{"id":"4","left":null,"next":{"id":"5","left":null,"next":{"id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"id":"7","left":{"ref":"5"},"next":null,"right":{"ref":"6"},"val":3},"right":{"ref":"4"},"val":2},"next":null,"right":{"ref":"7"},"val":1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

解析

解题思路

public List<List<Integer>> levelorderTraversalForIteration(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<TreeNode> deque = new LinkedList<>();

    if (root != null) deque.push(root);
    while (!deque.isEmpty()) {
        int dequeSize = deque.size();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < dequeSize; i++) {
            TreeNode node = deque.pollFirst();
            list.add(node.val);
            if (node.left!=null) deque.offerLast(node.left);
            if (node.right!=null) deque.offerLast(node.right);
        }
        ans.add(list);
    }
    return ans;
}
}

数据操作分析

  • 见思路分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

public class LeetCode0116_PopulatingNextRightPointersInEachNode {
    public Node connect(Node root) {

        if (root == null) return root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int layerSize = queue.size();
            Node last = null;
            //遍历当前层
            for (int i = 1; i <= layerSize; i++) {
                Node first = queue.poll();//取出队首元素
                if (first.left != null) queue.offer(first.left);
                if (first.right != null) queue.offer(first.right);
                if (i != 1) last.next = first;
                last = first;
            }

        }
        return root;
    }
}

官方解法

方法一：层次遍历

思路与算法：

题目本身希望我们将二叉树的每一层节点都连接起来形成一个链表。因此直观的做法我们可以对二叉树进行层次遍历，在层次遍历的过程中将我们将二叉树每一层的节点拿出来遍历并连接。

层次遍历基于广度优先搜索，它与广度优先搜索的不同之处在于，广度优先搜索每次只会取出一个节点来拓展，而层次遍历会每次将队列中的所有元素都拿出来拓展，这样能保证每次从队列中拿出来遍历的元素都是属于同一层的，因此我们可以在遍历的过程中修改每个节点的 next 指针，同时拓展下一层的新队列。

复杂度分析：

记树上的点的个数为 N。
1. 时间复杂度:O(N)。每个节点会被访问一次且只会被访问一次，即从队列中弹出，并建立 next 指针。
2. 空间复杂度：O(N)。这是一棵完美二叉树，它的最后一个层级包含 N/2 个节点。广度优先遍历的复杂度取决于一个层级上的最大元素数量。这种情况下空间复杂度为 O(N)。

编码实现

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }

        // 初始化队列同时将第一层节点加入队列中，即根节点
        Queue<Node> queue = new LinkedList<Node>(); 
        queue.add(root);

        // 外层的 while 循环迭代的是层数
        while (!queue.isEmpty()) {

            // 记录当前队列大小
            int size = queue.size();

            // 遍历这一层的所有节点
            for (int i = 0; i < size; i++) {

                // 从队首取出元素
                Node node = queue.poll();

                // 连接
                if (i < size - 1) {
                    node.next = queue.peek();
                }

                // 拓展下一层节点
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }

        // 返回根节点
        return root;
    }
}

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

思路：

  • 一棵树中，存在两种类型的 next 指针。
    • 第一种情况是连接同一个父节点的两个子节点。它们可以通过同一个节点直接访问到，因此执行下面操作即可完成连接。
      • node.left.next = node.right
    • 第二种情况在不同父亲的子节点之间建立连接，这种情况不能直接连接。
  • 如果每个节点有指向父节点的指针，可以通过该指针找到 next 节点。如果不存在该指针，则按照下面思路建立连接：

    第 NN 层节点之间建立 next 指针后，再建立第 N+1N+1 层节点的 next 指针。可以通过 next 指针访问同一层的所有节点，因此可以使用第 NN 层的 next 指针，为第 N+1N+1 层节点建立 next 指针。

算法：

  • 从根节点开始，由于第 00 层只有一个节点，所以不需要连接，直接为第 11 层节点建立 next 指针即可。该算法中需要注意的一点是，当我们为第 NN 层节点建立 next 指针时，处于第 N-1N−1 层。当第 NN 层节点的 next 指针全部建立完成后，移至第 NN 层，建立第 N+1N+1 层节点的 next 指针。
  • 遍历某一层的节点时，这层节点的 next 指针已经建立。因此我们只需要知道这一层的最左节点，就可以按照链表方式遍历，不需要使用队列。
  • 上面思路的伪代码如下：
leftmost = root
while (leftmost.left != null) {
    head = leftmost
    while (head.next != null) {
        1) Establish Connection 1
        2) Establish Connection 2 using next pointers
        head = head.next
    }
    leftmost = leftmost.left
}

  • 两种类型的 next 指针。
    • 第一种情况两个子节点属于同一个父节点，因此直接通过父节点建立两个子节点的 next 指针即可。node.left.next = node.right
    • 第二种情况是连接不同父节点之间子节点的情况。更具体地说，连接的是第一个父节点的右孩子和第二父节点的左孩子。由于已经在父节点这一层建立了 next 指针，因此可以直接通过第一个父节点的 next 指针找到第二个父节点，然后在它们的孩子之间建立连接。node.right.next = node.next.left
  • 完成当前层的连接后，进入下一层重复操作，直到所有的节点全部连接。进入下一层后需要更新最左节点，然后从新的最左节点开始遍历该层所有节点。因为是完美二叉树，因此最左节点一定是当前层最左节点的左孩子。如果当前最左节点的左孩子不存在，说明已经到达该树的最后一层，完成了所有节点的连接。

复杂度分析：

  1. 时间复杂度:O(N)。每个节点只访问一次。

  2. 空间复杂度：O(1)。不需要存储额外的节点。

编码实现

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }

        // 从根节点开始
        Node leftmost = root;

        while (leftmost.left != null) {

            // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
            Node head = leftmost;

            while (head != null) {

                // CONNECTION 1
                head.left.next = head.right;

                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }

                // 指针向后移动
                head = head.next;
            }

            // 去下一层的最左的节点
            leftmost = leftmost.left;
        }

        return root;
    }
}

精彩评论

跳转地址1：BFS解决（最好的击败了100%的用户）

BFS解决

思路：
  • 看到关于二叉树的问题，首先要想到关于二叉树的一些常见遍历方式，
    对于二叉树的遍历有

    • 前序遍历
    • 中序遍历
    • 后续遍历
    • 深度优先搜索（DFS）
    • 宽度优先搜索（BFS）
  • 除了上面介绍的5种以外，还有Morris（莫里斯）的前中后3种遍历方式，总共也就这8种。所以只要遇到二叉树相关的算法题，首先想到的就是上面的几种遍历方式，然后再稍加修改，基本上也就这个套路。
  • 这题让求的就是让把二叉树中每行都串联起来，对于这道题来说最适合的就是BFS。也就是一行一行的遍历，如下图所示
  • 代码如下：
    public Node connect(Node root) {
        if (root == null)
            return root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            //每一层的数量
            int levelCount = queue.size();
            //前一个节点
            Node pre = null;
            for (int i = 0; i < levelCount; i++) {
                //出队
                Node node = queue.poll();
                //如果pre为空就表示node节点是这一行的第一个，
                //没有前一个节点指向他，否则就让前一个节点指向他
                if (pre != null) {
                    pre.next = node;
                }
                //然后再让当前节点成为前一个节点
                pre = node;
                //左右子节点如果不为空就入队
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
        }
        return root;
    }
  • 如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历。
        } else if (cur->val < p->val && cur->val < q->val) {
            return traversal(cur->right, p, q);
        }
编码实现
  • 在遍历每一行的时候，只要把他们串联起来就OK，下面就来把上面的代码改造一下：
    public Node connect(Node root) {
        if (root == null)
            return root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            //每一层的数量
            int levelCount = queue.size();
            //前一个节点
            Node pre = null;
            for (int i = 0; i < levelCount; i++) {
                //出队
                Node node = queue.poll();
                //如果pre为空就表示node节点是这一行的第一个，
                //没有前一个节点指向他，否则就让前一个节点指向他
                if (pre != null) {
                    pre.next = node;
                }
                //然后再让当前节点成为前一个节点
                pre = node;
                //左右子节点如果不为空就入队
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
        }
        return root;
    }
优化思路：

  • 上面运行效率并不是很高，这是因为我们把节点不同的入队然后再不停的出队，其实可以不需要队列，每一行都可以看成一个链表比如第一行就是只有一个节点的链表，第二行是只有两个节点的链表（假如根节点的左右两个子节点都不为空）……

  • 经过上面的几步，很容易把链表给串起来，最后再来看下代码

优化后代码
     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 && cur.left != null) {
                //让pre节点的next指向当前节点的左子节点，也就是把它串起来
                pre.next = cur.left;
                //然后再更新pre
                pre = pre.next;

                //pre节点的next指向当前节点的右子节点，
                pre.next = cur.right;
                pre = pre.next;
                //继续访问这一行的下一个节点
                cur = cur.next;
            }
            //把下一层串联成一个链表之后，让他赋值给cur，
            //后续继续循环，直到cur为空为止
            cur = dummy.next;
        }
        return root;
    }

其他方式：

上面两种方式都是参照117. 填充每个节点的下一个右侧节点指针 II的题解，第117题不是完美二叉树，所以第117题的答案都可以拿到这里来用，但这里的答案却不能全部用在第117题。

我们还可以参照上面的方式来修改一下

    public Node connect(Node root) {
        if (root == null)
            return null;
        Node pre = root;
        Node cur = null;
        while (pre.left != null) {
            //遍历当前这一层的结点，然后把他们的下一层连接起来
            cur = pre;
            //cur不为空，就表示这一层还没遍历完，就继续循环
            while (cur != null) {
                //让下一层的左子节点指向右子节点
                cur.left.next = cur.right;
                //如果cur.next不为空，就表示还没遍历到这一层
                //最后的那个节点的右子节点，就让前一个结点的右
                //子节点指向下一个节点的左子节点
                if (cur.next != null)
                    cur.right.next = cur.next.left;
                //然后继续连接下一个节点的 子节点
                cur = cur.next;
            }
            //继续下一层
            pre = pre.left;
        }
        return root;
    }

递归

递归方式
或者也可以改为递归的 方式

    public Node connect(Node root) {
        dfs(root, null);
        return root;
    }

    private void dfs(Node curr, Node next) {
        if (curr == null)
            return;
        curr.next = next;
        dfs(curr.left, curr.right);
        dfs(curr.right, curr.next == null ? null : curr.next.left);
    }

跳转地址2：「手画图解」DFS 递归 | 易于理解

思路

首先，每个节点的next原本就指向null。

对于每个节点root，它的左孩子的next应该改指向它的右孩子（左右孩子肯定存在）。

它的右孩子的next怎么找到右邻居呢？——只要root.next存在（爸爸有右邻居），就能保证root.right有右邻居，让root.right.next指向root.next.left。

于是，对每个节点的处理逻辑：

root.left.next = root.right;  // 左孩子的next指向右孩子
if (root.next) {              // 如果当前root的next存在，说明右孩子有右邻居：root.next.left
  root.right.next = root.next.left;
}

递归从上往下，先处理当前节点，再处理它的左、右子树中的节点——前序遍历。

function dfs (root) {
  节点root的处理逻辑
  dfs(root.left)
  dfs(root.right)
}

什么时候结束递归呢？当遍历到叶子节点，它没有孩子，不存在孩子的next指向修改的问题。

if (root.left == null && root.right == null) {
  return;
}

编码实现

const connect = (root) => {
  if (root == null) {
    return root;
  }
  const dfs = (root) => {
    if (root.left == null && root.right == null) {
      return;
    }
    root.left.next = root.right;
    if (root.next) {
      root.right.next = root.next.left;
    }
    dfs(root.left);
    dfs(root.right);
  };
  dfs(root);
  return root;
};

复盘总结

对于整棵树的根节点，它的next是对的，不用修改。
下面的子节点的next是要修改的。所以可以用 DFS，从上往下去修改。
左孩子的next肯定要修改，右孩子的next可能要修改。
后者的修改，需要有一个前提——自己的next要存在，右孩子才能找到右邻居。

US-B.Ralph
LeetCode数据结构与算法算法

One Comment

  • 샌즈카지노

    Im thankful for the post. Really thank you! Fantastic. Claudette Alisander Senzer

    Reply

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

4 × 2 =