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

题目描述

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
相关话题： 树、深度优先搜索    难度： 中等

示例

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

• 解法1
  刚看到这道题，我想到的是二叉树的层次遍历，通过一个current指针跟踪 next指针的填充进度。
  需要注意的是一个边界情况：该节点是该层的第一个节点
  
  
  每次从队列中弹出一个Node x,current.next指向x完成next的填充，所以弹出的x==begin时自然要特殊处理，因为它的左边没有节点。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    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) {
        if(root == null) return null;
        Node begin = root;
        Node end = root;
        Node current = root;
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node x = queue.poll();
            if(x == begin){//如果当前节点是该层第一个节点，begin更新为下
                           //一层的第一个节点，current = x
                begin = x.left;
                current = x;
            }else{//如果不是第一个节点，x就会被current.next指向
                current.next = x;
                current = current.next;//current跟进
            }
            if(x == end){//如果x是最后一个节点，那么end更新为下一层的最后一个节点
                end = x.right;
            }
            //下一层入队
            if(x.left != null){
                queue.offer(x.left);
            }
            if(x.right != null){
                queue.offer(x.right);
            }
        }
        return root;
    }
}

该方法的额外空间并不符合题目要求，题目要求常数级空间。

• 解法2
  
  
  思路：递归版本简单明了，遍历到当前节点，如图如遍历到2节点，
• 如果root.left != null也就是说该节点有左右孩子，那么就root.left.next = root.right;，让左孩子指向右孩子。
• 如果root.next != null该节点的next不为空，让右孩子指向它的next的左孩子root.right.next = root.next.left;。
• 对左右孩子做递归操作。

     public Node connect(Node root) {
         if(root == null) return null;
         if(root.left!=null){
             root.left.next = root.right;
             if(root.next != null)
                 root.right.next = root.next.left;
         }
         connect(root.left);
         connect(root.right);
         return root;
     }