本文共 2513 字，大约阅读时间需要 8 分钟。

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {  int val;  Node *left;  Node *right;  Node *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.

Follow up:

You may only use constant extra space. Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

我的想法

用BFS层次遍历，定义一个queue存每层的结点，prev指向前一个结点，如果prev不为空，则prev的next为当前结点。follow up的意思是只能用常数的额外空间，递归所产生的隐式栈空间也算做常数额外空间。因此follow up不能用queue来动态的存储层结点。没想出来follow up该怎么做

class Solution {
       public Node connect(Node root) {
           if(root == null) {
               return root;        }        Deque
   
     queue = new LinkedList<>();        queue.offerLast(root);        while(!queue.isEmpty()) {
               int size = queue.size();            Node prev = null;            for(int i = 0; i < size; i++) {
                   Node node = queue.pollFirst();                if(prev != null) {
                       prev.next = node;                }                if(node.left != null) {
                       queue.offerLast(node.left);                }                if(node.right != null) {
                       queue.offerLast(node.right);                }                prev = node;            }        }        return root;    }}
   

解答

jiuzhang solution:

边串next，边利用next

class Solution {
       public Node connect(Node root) {
           Node prev = null, next = null, parent = root;        //控制上下层        while(parent != null) {
               //控制一层内的结点            while(parent != null) {
                   //next控制转下一层                if(next == null) {
                       next = parent.left == null ? parent.right : parent.left;                }                if(parent.left != null) {
                       if(prev != null) {
                           prev.next = parent.left;                    }                    prev = parent.left;                }                if(parent.right != null) {
                       if(prev != null) {
                           prev.next = parent.right;                    }                    prev = parent.right;                }                parent = parent.next;            }            parent = next;            prev = null;            next = null;        }        return root;    }}

转载地址：http://dyqvb.baihongyu.com/