Populating Next Right Pointers in Each Node
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Populating Next Right Pointers in Each Node,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1545字,纯文字阅读大概需要3分钟。
内容图文
![Populating Next Right Pointers in Each Node](/upload/InfoBanner/zyjiaocheng/1265/e3213d67239546b4997e21c6a841579d.jpg)
Populating Next Right Pointers in Each Node
问题:
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
.
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)
思路:
采用队列方法,poll队首的同时,加入两个其孩子
核心是记录每一个层次的大小,两层循环,时间复杂度为O(n)
我的代码:
![技术分享](/upload/getfiles/default/2022/11/13/20221113035638091.jpg)
![技术分享](/upload/getfiles/default/2022/11/13/20221113035638152.jpg)
public class Solution { public void connect(TreeLinkNode root) { if(root == null) return ; LinkedList<TreeLinkNode> ll = new LinkedList<TreeLinkNode>() ; ll.add(root) ; while(!ll.isEmpty()) { int size = ll.size() ; TreeLinkNode pre = ll.poll() ; if(pre.left != null) ll.add(pre.left) ; if(pre.right != null) ll.add(pre.right) ; for(int i = 0 ; i < size - 1 ; i++) { TreeLinkNode tmp = ll.poll() ; pre.next = tmp ; if(tmp.left != null) { ll.add(tmp.left) ; } if(tmp.right != null) { ll.add(tmp.right) ; } pre = pre.next ; } pre.next = null ; } } }
他人代码:
![技术分享](/upload/getfiles/default/2022/11/13/20221113035638091.jpg)
![技术分享](/upload/getfiles/default/2022/11/13/20221113035638152.jpg)
public void connect(TreeLinkNode root) { if (root == null) { return; } TreeLinkNode leftEnd = root; while (leftEnd != null && leftEnd.left != null) { TreeLinkNode cur = leftEnd; while (cur != null) { cur.left.next = cur.right; cur.right.next = cur.next == null ? null: cur.next.left; cur = cur.next; } leftEnd = leftEnd.left; } }
学习之处:
- 自己的方法不足之处在于空间复杂度为O(n),而他人方法的空间复杂度为O(1)
- 他人方法的思路为使用2个循环,一个指针P1专门记录每一层的最左边节点,另一个指针P2扫描本层,把下一层的链接上
原文:http://www.cnblogs.com/sunshisonghit/p/4313511.html
内容总结
以上是互联网集市为您收集整理的Populating Next Right Pointers in Each Node全部内容,希望文章能够帮你解决Populating Next Right Pointers in Each Node所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。