LeetCode第116题

LC 第116题

给定一个完美二叉树，填充每一个节点的next指针。节点定义

class Node {
  public int val;
  public Node left;
  public Node right;
  public Node next;
}

方法一

基于广度优先搜索，不同的是，每次都取出一层的所有节点。遍历当前层数节点，将每个节点的next都指向当前队列中的节点，而最后一个指向null

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();
    // 遍历当前层数
    for (int i = 0; i < size; i ++) {
      // 取出队首的节点
      Node n = queue.poll();
      // 当当前遍历的元素不是倒数第一个时，即i此时要小于size-1,则查看队头节点，并且把当前节点的next指向它
      if (i < size - 1) {
        Node head = queue.peek();
        n.next = head;
      }
      // 将左右子节点放入队列中
      if (n.left != null) {
        queue.offer(n.left);
      }
      
      if (n.right != null) {
        queue.offer(n.right);
      }
    }
  }
  return root;
}

方法二

当前节点为根节点时，next = null；

next都是由left 指向right的，而对于第三层开始，除了left.next = right之外， right.next = 上一节点.next.left

public Node connect(Node root) {
  // 出口
  if (root == null) return null;
  // 判断当前节点的左节点是否为空，如果不为空的话就将left.next = right
  if (root.left != null) {
    root.left.next = root.right.next;
    // 如果当前节点的next不为空
    if (root.next != null) {
      root.right.next = root.next.left;
    }
  }
  // 递归
  connect(root.left);
  connect(root.right);
  return root;
}