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

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

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

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

【leetcode|leetcode 116. 填充每个节点的下一个右侧节点指针】示例

文章图片

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

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

解法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 queue = new LinkedList(); 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; }