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
Solution 1:
递归版本。
public void connect(TreeLinkNode root) { if(root == null) return; TreeLinkNode p = root.next; while(p!=null) { if(p.left != null) { p = p.left; break; } if(p.right != null) { p = p.right; break; } p = p.next; } if(root.right != null) { root.right.next = p; p = root.right; } if(root.left != null) { root.left.next = p; } connect(root.right); connect(root.left); }
Solution 2:
非递归版本。
public void connect(TreeLinkNode root) { if(root == null) return; TreeLinkNode lastHead = root; TreeLinkNode curHead = null, curPrev = null; while(lastHead!=null) { while(lastHead != null) { if(lastHead.left!=null) { if(curHead == null) { curHead = lastHead.left; curPrev = curHead; } else { curPrev.next = lastHead.left; curPrev = curPrev.next; } } if(lastHead.right!=null) { if(curHead == null) { curHead = lastHead.right; curPrev = curHead; } else { curPrev.next = lastHead.right; curPrev = curPrev.next; } } lastHead = lastHead.next; } lastHead = curHead; curHead = null; } }
相关推荐
leetcode卡 leetcode_python 项目介绍 想学学python,刷刷leetcode 打卡轨迹 2020-01-13 70 爬楼梯 2020-01-14 120 Triangle 2020-01-15 213 House Robberll -变种 198 337 2020-01-16 139 单词拆分 2020-01-20 104 ...
力扣C++刷题指南教程,总结归纳得很不错
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案解析 golang解答
leetcode 答案leetcode--python Leetcode 的答案
leetcode-pp-node 官网后端。 使用 koa2 结合 Github Actions 开发。目前采用静态 JSON 存放题解,讲义,用户信息等数据,后期使用数据库承载内容。 TODOS 在 91 网站直接提交代码到力扣中,获取执行结果并在 91 中...
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
四平方和定理 leetcode Leetcode practice Table of content Tree 92.reverse-linked-list-ii (反转链表 II) 94.binary-tree-in...116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点
leetcode 1 -200题所有源码 有问题私聊我
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为