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

  • 双指针
  • 递归

本题使用层序遍历使用队列可以十分轻松的解决，由于题目中需要常数级别的空间复杂度，因此不使用该方法。按照本题题干中的提示，递归的调用栈所占空间不算空间复杂度。因此使用递归。

本题使用递归（前序遍历）方法解决：

  1. 边界条件
    如果根节点为null，则返回

  2. 递归过程
    为根节点的两个孩子节点找到next

    左孩子节点找next：由于是完全二叉树，因此父节点一定包含左右两个孩子节点，root.left.next = root.right; 如果该节点为叶子节点则直接返回。

    右孩子节点找next：如果根节点root的next存在的话；则右孩子节点的next为root.next的左孩子节点。即root.right.next = root.next.left;

    递归执行root.left和root.right

/*
// Definition for a Node.
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;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        conn(root);
        return root;
    }

    public void conn(Node root){
        if(root == null){
            return;
        }
        if(root.left != null && root.right != null){
            root.left.next = root.right;
        }else{
            return;
        }
        if(root.next != null){
            root.right.next = root.next.left;
        }
        conn(root.left);
        conn(root.right);
    }
}