问题描述:
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
原问题链接:https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
问题分析
这个问题和前面的那个问题类似,因为不能借助任何其他的集合类的结构来帮助遍历树,而且树的结构也不像前面所描述的那样是一棵完美二叉树,那么这将意味着不是每个节点都包含有两个子节点的,有的可能有一个,也可能一个都没有。这个问题如果不结合一个具体的示例来推导的话,会显得非常的困难。
我们就以问题描述里的示例为基础,这个树的结构如下图:
我们最开始遍历的时候,肯定需要找到根节点。然后通过根节点去串联它下面的子节点。那么,当我们有一个引用指向根节点的时候,该怎么去串联它的子节点呢?因为它的子节点是不一定就存在的。而且,我们首先就需要找到它的那个存在的子节点才行,这样才能想办法将它所有可以访问到的子节点那一层都串起来。
有一个如下的办法可以解决,就是我们首先建立一个dummy节点,这个节点在某一层的节点遍历过程中指向它所有碰到过的非空节点,然后再根据循环中碰到的元素依次往前。这样相当于上面的节点遍历一遍之后也将它下面一层的节点给串起来了。详细的过程如下图:
首先我们建立了一个dummy节点,让它的next指向root节点。这样我们设置额外的两个节点分别为pre, n,它们的指向如下:
我们在设定了这个之后,再将当前节点的next引用设置为null。在我们从n开始往它的next去遍历时,我们在碰到非空的节点时,将pre的next节点和n的非空节点串起来。所以在上图中,当碰到节点2的时候,则情况如下:
因为前面将cur和pre设置为同一个引用,所以这一步就将它们的next引用指向了同一个节点。但在这一步找到一个节点之后,我们就将pre沿着next前进一步,如下图:
同样,如果我们碰到下一个非空的子节点呢,则继续将pre和前面串起来,如下图所示:
因此,上述过程可以概括成在n往next方向循环遍历的时候,判断它的左右子节点,如果有一个不为空,则pre.next = 这个不空的节点,然后再将pre = pre.next这样往前移。
这里还有一个问题就是,在一层遍历完之后,如果我们还需要去遍历下一层,就需要用到cur这个临时节点,我们需要将pre = cur,然后将cur.next赋值给n。然后再将cur, pre都设置为null。n再依次往next方向去遍历。这样直到我们的cur节点的next引用为空为止。所以上述过程中,cur节点起到一个记录点的作用,它的当前点作为下一个层次遍历的引用起始点,它的next节点作为下一层遍历的父节点。
按照前面的讨论,详细的代码实现如下:
/** * 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) { TreeLinkNode nextHead = new TreeLinkNode(0); nextHead.next = root; while(nextHead.next != null) { TreeLinkNode tail = nextHead; TreeLinkNode n = nextHead.next; nextHead.next = null; for(; n != null; n = n.next) { if(n.left != null) { tail.next = n.left; tail = tail.next; } if(n.right != null) { tail.next = n.right; tail = tail.next; } } } } }
相关推荐
lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary...
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode卡leetcode 算法 :smiling_face_with_sunglasses: 9月打卡 问题 困难 标签 Medium Minimax Dynamic Programming Medium Minimax Dynamic Programming Math Hard BackTracking Easy Tree Depth-first Search ...
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
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 ...
蓄水池算法 leetcode leetcode Post: 《双指针的魅力》 《常见面试题思想方法整理》 ...populating-next-right-pointers-in-each-node-ii: 二级指针代码虽然简洁优雅,但是对性能有影响,不如一级指针加if else判断快。
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
leetcode 2 和 c 一个让你谦卑的错误,胜过让你傲慢的成就。 leetcode 解决方案 :construction: 我的 Leetcode 算法问题练习解决方案使用 C#(.Net Core)并使用 MSUnit 进行测试。 希望它可以帮助任何人进行技术...
LeetCode 101:和你一起你轻松刷题(C++)
Leetcode:Leetcode提交
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
Algorithm-In-Leetcode To solve algorithm problems in leetcode.com using Python, Golang and SQL It's my leetcode account: 这是我的LeetCode中文账户: 不仅仅是Algorithm,还有Database的题目也包含在内。题目...
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
leetcode:leetcode刷题
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
LeetCode 解决VS Code中的LeetCode问题 英文文件| 文件 :exclamation_mark: 注意 :exclamation_mark: -登录LeetCode端点的解决方法注意:如果使用的是leetcode-cn.com ,则可以忽略此部分。 最近,我们发现。 此问题...