Populating Next Right Pointers in Each Node I

Given a binary tree

struct TreeLinkNode {  TreeLinkNode *left;  TreeLinkNode *right;  TreeLinkNode *next;}

Populate each next pointer to point to its next right node. If there
is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.
For example, Given the following binary tree,

     1   /  \  2    3 / \    \4   5    7

After calling your function, the tree should look like:

     1 -> NULL   /  \  2 -> 3 -> NULL / \    \4-> 5 -> 7 -> NULL

Note:

You may only use constant extra space. You may assume that it is a
perfect binary tree (ie, all leaves are at the same level, and every
parent has two children).

原题链接

广度优先搜索

复杂度

时间 O(N) 空间 O(N)

思路

相当于是Level Order遍历二叉树。通过一个Queue来控制每层的遍历，注意处理该层最后一个节点的特殊情况。此方法同样可解第二题。

代码

/**

• Definition for binary tree with next pointer.

• public class TreeLinkNode {

• int val;

• TreeLinkNode left, right, next;

• TreeLinkNode(int x) { val = x; }

• }
  */

  public class Solution {

  public void connect(TreeLinkNode root) {

     Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();   if(root!=null) q.offer(root);   while(!q.isEmpty()){       //记录本层节点的个数       int size = q.size();       for(int i = 0; i < size; i++){           TreeLinkNode curr = q.poll();           //最后一个节点的next是null，不做处理           if(i < size - 1){   TreeLinkNode next = q.peek();   curr.next = next;           }           if(curr.left != null) q.offer(curr.left);           if(curr.right != null) q.offer(curr.right);       }   }

  }

  }

递归法

复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

由于父节点多了next指针，我们不用记录父节点的父节点就能直到它相邻的节点。对于左子节点来说，其next节点就是父节点的右节点。对于右子节点来说i，其next节点就是父节点的next节点的左子节点。以此递归。

代码

/**

• Definition for binary tree with next pointer.

• public class TreeLinkNode {

• int val;

• TreeLinkNode left, right, next;

• TreeLinkNode(int x) { val = x; }

• }

双指针法 Two Pointers

复杂度

时间 O(N) 空间 O(1)

思路

上述两种方法都会使用额外空间。实际上，我们可以用一个指针记录当前层内遍历到的节点，另一个指针记录下一层第一个节点，来省去空间开销。这样，我们可以基于上一层的next指针进行横向遍历，同时遍历到该层尽头时又能使用记录下的下一层第一个节点的指针来直接跳转到下一层。

代码

public class Solution {    public void connect(TreeLinkNode root) {        if(root == null) return;        //记录该层当前节点的指针，也叫做父节点，我们通过遍历父节点，来连接它们的子节点        TreeLinkNode p = root;        //记录下层第一个节点的指针        TreeLinkNode first = null;        while(p != null){//当first为空时，说明刚跳转到新的一层，需要设置下一层的第一个节点了if(first == null){    first = p.left;}//如果有左子节点，则其next是右子节点，如果没有，则遍历结束//因为我们实际上是将下一层的节点用next指针连接，所以当遍历到叶子结点时已经没有下一层if(p.left != null){    p.left.next = p.right; } else {    break;}//如果父节点有next，则next的左子节点是父节点的右子节点的next，如果没有，说明这层遍历完了，转入下一层if(p.next != null){    p.right.next = p.next.left;    p = p.next;} else {    p = first;    first = null;}        }    }}

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous
solution still work?

Note:

You may only use constant extra space. For example, Given the
following binary tree,

     1   /  \  2    3 / \    \4   5    7 

After calling your function, the tree should look like:

     1 -> NULL   /  \  2 -> 3 -> NULL / \    \4-> 5 -> 7 -> NULL

原题链接

递归法

复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

由于父节点多了next指针，我们不用记录父节点的父节点就能直到它相邻的节点。对于左子节点来说，其next节点就是父节点的右节点。对于右子节点来说i，其next节点就是父节点的next节点的左子节点。以此递归。

代码

public class Solution {    public void connect(TreeLinkNode root) {        if(root == null) return;        if(root.left != null) root.left.next = root.right;        if(root.right != null){root.right.next = root.next == null? null:root.next.left;        }        connect(root.left);        connect(root.right);    }}

三指针法 Three Pointers

复杂度

时间 O(N) 空间 O(1)

思路

当不是完全二叉树时，左子节点或者右子节点都有可能为空，每个叶子节点的深度也不一定相同，所以退出循环的条件、每层头节点的确定方法以及next指针的赋值都要改变。首先，next指针不再是分左右子节点来直接赋值，而是对记录下来的上个节点的next赋当前操作的节点。其次，退出循环不能再像上一题一样到最后一层就可以退出，因为当前节点会不断更新，只有当前节点为空时才能退出。最后头节点可能是左子节点，也可能是右子节点。

代码

public class Solution {    public void connect(TreeLinkNode root) {        if(root == null) return;        TreeLinkNode p = root;        TreeLinkNode first = null;        //上一个节点，我们给上一个节点的next赋值，然后再更新上一个节点为它的next        TreeLinkNode last = null;        while(p != null){//下一层的头节点有可能是左子节点也有可能是右子节点if(first == null){    if(p.left != null){        first = p.left;    } else if(p.right != null){        first = p.right;    }}//更新last和last的nextif(p.left != null){    if(last != null){        last.next = p.left;    }    last = p.left;}if(p.right != null){    if(last != null){        last.next = p.right;    }    last = p.right;}//如果当前节点没有next，则该层结束，转入下一层，否则就继续if(p.next != null){    p = p.next;} else {    p = first;    first = null;    last = null;}        }    }}