首页 > 试题广场 >

填充每个节点指向最右节点的next指针 ii

[编程题]填充每个节点指向最右节点的next指针 ii
  • 热度指数:16141 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
继续思考"填充每个节点指向最右节点的next指针" 这道题
如果给定的树可以是任意的二叉树呢?你之前的给出的算法还有效吗?
注意:
  • 你只能使用常量的额外内存空间
例如:
给出的二叉树如下:

调用完你给出的函数之后,这棵树应该变成:



说明:本题目包含复杂数据结构TreeLinkNode,点此查看相关信息
核心思路:
如果当前层所有结点的next 指针已经设置好了,那么据此,下一层所有结点的next指针 也可以依次被设置。
class Solution 
{
public:
    void connect(TreeLinkNode *root) 
	{
        while(root)
		{
			TreeLinkNode dummy(-1), *prev;
			prev = &dummy;
			for(auto p = root; p; p = p->next)
			{
				if(p->left)
				{
					prev->next = p->left;
					prev = prev->next;
				}
				if(p->right)
				{
					prev->next = p->right;
					prev = prev->next;
				}
			}
			root = dummy.next; // 指向下一层的第一个节点
		}
    }
};

发表于 2016-08-10 22:01:03 回复(11)
public void connect(TreeLinkNode root) {
		while (root != null) {
			//tmpLevelFirst为新建立的每层第一个节点(为了方便后面遍历当前行节点)
			TreeLinkNode tmpLevelFirst = new TreeLinkNode(0);
			TreeLinkNode cur = tmpLevelFirst;
			while (root != null) {
				if (root.left != null) {
					cur.next = root.left;
					cur = cur.next;
				}
				if (root.right != null) {
					cur.next = root.right;
					cur = cur.next;
				}
				root = root.next;
			}
			root = tmpLevelFirst.next;
		}
	}

发表于 2017-08-09 10:35:14 回复(3)

看了下讨论区的代码,几乎都没达到常量内存空间的要求;

class Solution {
public:
   void connect(TreeLinkNode *root) {
    TreeLinkNode*cur = root;
    TreeLinkNode*pre;
    int count = 1;
    while (cur){
        bool flag = true;
        for (auto p = cur; p; p = p->next){
            if (p->left){
                if (flag){
                    cur = p->left;
                    flag = false;
                    pre = p->left;
                }
                else{
                    pre->next = p->left;
                    pre = pre->next;
                }

            }
            if (p->right){
                if (flag){//第一次进入该层
                    cur = p->right;
                    flag = false;
                    pre = p->right;
                }
                else{
                    pre->next = p->right;
                    pre = pre->next;
                }

            }
        }
        if (flag)//如果没进入for循环说明cur已经是最后一层
            return;
    }
}
};
发表于 2018-05-27 20:58:16 回复(2)
class Solution {
public:
    void connect(TreeLinkNode *root) {
        //利用层序遍历思想,需要注意的是对每层的节点都进行处理
        if(root==NULL) return;
        queue<TreeLinkNode*> que;
        que.push(root);
        while(!que.empty()){
            int n=que.size();
            for(int i=0;i<n;i++){
                TreeLinkNode* tmp=que.front();
                que.pop();
                if(tmp->left) que.push(tmp->left);
                if(tmp->right) que.push(tmp->right);
                if(i!=n-1) tmp->next=que.front();
                else tmp->next=NULL;
            }
        }
    }
};

这个问题我们可以通过二叉树的层序遍历进行解决,需要注意的是,对每一层的节点进行对应的层序遍历!
发表于 2017-12-12 22:08:52 回复(4)
所以告诉我为什么问题一和问题二我用同一份代码就都过了。。。
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null)
			return;
		Queue<TreeLinkNode> queue = new LinkedList<>();
		queue.offer(root);
		
		while(!queue.isEmpty()){
			int len = queue.size();
			for(int i = 0; i < len; i++){
				TreeLinkNode tmp = queue.poll();
				if(i == len - 1){
					tmp.next = null;
				}else {
					tmp.next = queue.peek();
				}
				if(tmp.left != null)
					queue.offer(tmp.left);
				if(tmp.right != null)
					queue.offer(tmp.right);
			}				
		}
    }
}

发表于 2017-05-07 10:30:03 回复(8)
import java.util.*;
// 层次遍历,记录每一层的结点个数,循环设置next指针
public void connect(TreeLinkNode root) {
		if(root == null) return;
		Queue<TreeLinkNode> queue = new LinkedList<>();
		queue.add(root);
		int curCount = 1;
		int nextCount = 0;
		while ( ! queue.isEmpty()) {
			TreeLinkNode[] arr = new TreeLinkNode[curCount]; // 存放一层结点
			for (int i = 0; i < curCount; i ++) {
				TreeLinkNode curNode = queue.poll();
				arr[i] = curNode;
				if(curNode.left != null) {
					queue.add(curNode.left);
					nextCount ++;
				}
				if(curNode.right != null) {
					queue.add(curNode.right);
					nextCount ++;
				}
			}
			for (int i = 0; i < arr.length - 1; i ++) {
				arr[i].next = arr[i + 1];
			}
			curCount = nextCount;
			nextCount = 0;
		}
	}

编辑于 2017-03-19 22:27:33 回复(0)
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL)
            return;
        //层次遍历
        queue<TreeLinkNode*> q;
        q.push(root);
        TreeLinkNode* curNode = NULL;
        TreeLinkNode* nextNode = NULL;
        while(! q.empty()){
            //和一般的层次遍历略有不同,每次while要把当前层的节点全部弹出去
            int len = q.size();
            curNode = q.front();
            q.pop();
            if(curNode->left != NULL)
                q.push(curNode->left);
            if(curNode->right != NULL)
                q.push(curNode->right);
            for(int i = 1;i<len;++i){
                nextNode = q.front();
                q.pop();
                curNode->next = nextNode;
                curNode = nextNode;
                if(curNode->left != NULL)
               		q.push(curNode->left);
          	    if(curNode->right != NULL)
                	q.push(curNode->right);
            }
		    curNode->next = NULL;
        }
    }
};

发表于 2016-08-31 18:30:13 回复(0)
// Two Solutions
class Solution {
public:
  // DFS
  void connect(TreeLinkNode* root) {
    int max_depth = -1;
    vector<TreeLinkNode*> nexts;
    function<void(TreeLinkNode*, int)> DFS =
        [&](TreeLinkNode* r, int d) -> void {
      
      if (!r) return;
      if (d > max_depth) {
        nexts.emplace_back(r);
        max_depth = d;
      } else {
        r->next = nexts[d];
        nexts[d] = r;
      }
      DFS(r->right, d + 1);
      DFS(r->left,  d + 1);
    };
    
    DFS(root, 0);
  }
  
  // BFS
  void connectII(TreeLinkNode *root) {
    // corner case
    if (!root) return;
    
    queue<TreeLinkNode*> q{{root}};
    while (not q.empty()) {
      size_t s = q.size();
      TreeLinkNode* pre = nullptr; 
      while (s--) {
        auto curr = q.front(); q.pop();
        if (pre) pre->next = curr;
        if (curr->left) q.emplace(curr->left);
        if (curr->right) q.emplace(curr->right);
        pre = curr;
      }
    }
  }
};

发表于 2021-09-13 18:52:14 回复(0)
/**
 * 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) {
        while(root != null){
            TreeLinkNode dummy = new TreeLinkNode(0);
            TreeLinkNode cur = dummy;
            while(root != null){
                if(root.left != null){
                    cur.next = root.left;
                    cur = cur.next;
                }
                if(root.right != null){
                    cur.next = root.right;
                    cur = cur.next;
                }
                root = root.next;
            }
            root = dummy.next;
        }
    }
}

发表于 2020-10-06 10:15:25 回复(0)
leetcode原题提示:
  • 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.
也就是说可以通过递归实现,通过虚拟机栈去保存和传递数据,从而省下来自己在堆里划分一个辅助容器。
/**
 * 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 TreeLinkNode connect(TreeLinkNode root) {
        TreeLinkNode head = root;
        while(head!=null){
            // 递归构造每一层的链表:从最左边元素连到最右边元素
            // 当前节点是当前层的最左边节点,返回的是子节点一层的最左边节点
            head = findNext(head, head.next);
        }
        return root;
    }
    // 子节点的最右边元素,是父节点的右边元素的子节点的最左边元素
    // 返回当前节点子节点的最左边元素
    public TreeLinkNode findNext(TreeLinkNode node, TreeLinkNode pNext){
        TreeLinkNode next = null;
        if(pNext!=null) {
            next = findNext(pNext, pNext.next);
        }
        if(node.right!=null){
            node.right.next = next;
            next = node.right;
        }
        if(node.left!=null){
            node.left.next = next;
            next = node.left;
        }
        return next;
    }
}


编辑于 2020-01-11 11:46:49 回复(0)
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(!root)return;
        queue<TreeLinkNode*>que;
        que.push(root);
        while(!que.empty()){
            int len=que.size();
            for(int i=0;i<len;i++){
                TreeLinkNode* cur=que.front();
                que.pop();
                if(i!=len-1)
                    cur->next=que.front();
                if(cur->left)que.push(cur->left);
                if(cur->right)que.push(cur->right); 
            }
        }
    }
};

发表于 2019-08-20 18:14:27 回复(0)
和上一题基本上一样。
唯一的区别就是每一层的节点数不一样了。
把下一层的节点数统计出来。每次往队列中添加节点时,把计数器加一即可。
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        int n = 1;    //这一行的个数。
        int row = 0;  //行号。
        int loc = 0;  //当前位置。
        int next = 0;
        TreeLinkNode pre = null;    //前一个节点。
        Stack<TreeLinkNode> stack = new Stack<>();
        Queue<TreeLinkNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            loc++;
            TreeLinkNode node = queue.poll();
            if (pre != null) pre.next = node;
            if (node.left != null) {
                queue.offer(node.left);
                next++;
            }
            if (node.right != null) {
                queue.offer(node.right);
                next++;
            }
            if (loc == n) {
                node.next = null;
                row++;
                n = next;
                next = 0;
                loc = 0;
                pre = null;
            } else {
                pre = node;
            }
        }
    }
}

发表于 2019-06-17 16:30:49 回复(0)
//常量空间 三个指针
class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode *p = NULL, *cur = NULL, *f = root;
        while(f){
            p = f;
            cur = NULL;
            while(!cur && p){
                if(p -> right && p -> left) {p -> left -> next = p -> right; cur = p -> right;}
                else if(p -> left)  cur = p -> left;
                else if(p -> right) cur = p -> right;
                p = p -> next;
            }
            while(p){
                if(p -> right && p -> left) { 
                    cur -> next = p -> left;
                    p -> left -> next = p -> right; 
                    cur = p -> right;
                }
                else if(p -> left)  {cur -> next = p -> left;  cur = p -> left;}
                else if(p -> right) {cur -> next = p -> right; cur = p -> right;}
                p = p -> next;
            }
            
            while(f){
                if(f -> left) {f = f -> left; break;}
                else if (f -> right) {f = f -> right; break;}
                f = f -> next;
            }
        }
        return ;
    }
}; 

发表于 2019-04-05 11:22:50 回复(0)
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL)
        {
            return ;
        }
        TreeLinkNode *node1,*node2;
        queue<TreeLinkNode*> que;
        que.push(root);
        int count = 0;
        while(!que.empty())
        {
            count = que.size();
            node1=que.front();
            que.pop();
            if(node1->left != NULL)
                que.push(node1->left);
            if(node1->right != NULL)
            {
                que.push(node1->right);
            }
            count--;
            while(count-- > 0)
            {
                node2 = que.front();
                que.pop();
                if(node2->left != NULL)
                    que.push(node2->left);
                if(node2->right != NULL)
                    que.push(node2->right);
                node1->next = node2;
                node1 = node2;
            }
            node1->next = NULL;
        }
    }
};

发表于 2018-08-20 17:32:36 回复(0)
class Solution {
public:
    void connect(TreeLinkNode *root) {
        while(root){
            TreeLinkNode head(0);
            TreeLinkNode *pre=&head,*p;
            for(p=root;p;p=p->next){
                if(p->left)
                    pre->next=p->left,pre=p->left;
                if(p->right)
                    pre->next=p->right,pre=p->right;
            }
            root=head.next;
        }
    }
};

发表于 2018-05-27 19:58:14 回复(0)
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {       
        while(root){
            TreeLinkNode temp(-1),*pre;
            pre=&temp;
            for(auto p=root;p;p=p->next){
                if(p->left){
                    pre->next=p->left;
                    pre=pre->next;
                }
                if(p->right){
                    pre->next=p->right;
                    pre=pre->next;
                }
            }
            root=temp.next;
        }
    }
};
发表于 2018-04-08 18:36:32 回复(0)
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
//肯定有同学和我的想法一样,用上一题的思路来做。但是要注意先递归右孩子,再递归左孩子。
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root)
            return;
        TreeLinkNode *p=root->next,*q=NULL;
        while (p!=NULL){
            if (p->left==NULL && p->right==NULL){
                p=p->next;continue;
            }
            if (p->left!=NULL) {
                q=p->left;
                break;
            }
            if (p->right!=NULL) {
                q=p->right;
                break;
            }
        }
        if (root->left&&root->right){
            root->left->next=root->right;
            root->right->next=q;
        }
        else if(root->left&&!root->right){
            root->left->next=q;
        }
        else if(!root->left&&root->right){
            root->right->next=q;
        }
        else 
            return;
        connect(root->right);
        connect(root->left);
        
    }
};
发表于 2018-01-23 20:44:23 回复(0)
//类似BFS的思想
class Solution {
public:
    void connect(TreeLinkNode *root) {
         while(root){
              TreeLinkNode dummy(-1),*pre=&dummy;
              while(root){
                   if(root->left) pre->next=root->left,pre=pre->next;
                   if(root->right) pre->next=root->right,pre=pre->next;
                   root=root->next;
              }
              root=dummy.next;
         }
    }
};

发表于 2017-08-20 19:26:53 回复(0)
class Solution {
public:
    void connect(TreeLinkNode *root) {
        while(root)
        {
        	TreeLinkNode L(-1),*f,*p;
        	f = &L;
        	p = root;
        	while(p)
        	{
        		if(p->left != NULL)
        		{
        			f->next = p->left;
        			f = f->next;
				}
				if(p->right != NULL)
				{
					f->next = p->right;
					f = f->next;
				}
				p = p->next;
			}
			root = L.next;
		}
    }
};


发表于 2017-08-17 01:25:45 回复(0)
/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
//层次遍历  记录每层的节点个数 并将一层元素存到一个临时数组中 遍历数组添加右指针
import java.util.*;
public class Solution {
    public void connect(TreeLinkNode root) {
        
        if(root == null){
            return;
        }
        
        int cur=1;
        int next=0;
        
        LinkedList<TreeLinkNode> list=new LinkedList<TreeLinkNode>();
        list.add(root);
        
        while(!list.isEmpty()){
            
            TreeLinkNode temp[]=new TreeLinkNode[cur];
            
            for(int i=0;i<cur;i++){
                
                temp[i]=list.poll();
                
                if(temp[i].left!=null){
                    next++;
                    
                    list.add(temp[i].left);
                }
                if(temp[i].right!=null){
                    next++;
                    
                    list.add(temp[i].right);
                }
                
            }
            
            for(int i=1;i<cur;i++){
                
                temp[i-1].next=temp[i];
                
            }
            
            cur=next;
            next=0;
            
            
            
            
        }
        
        
        
       
    }
}
发表于 2017-08-13 13:15:32 回复(0)