问题描述:
Given a binary tree
struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *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
.
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).
For example,
Given the following perfect binary tree,
1 / \ 2 3 / \ / \ 4 5 6 7
After calling your function, the tree should look like:
1 -> NULL / \ 2 -> 3 -> NULL / \ / \ 4->5->6->7 -> NULL
原问题链接:https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
问题分析
这个问题的要求相对来说比较严格,因为要求有常量个的额外空间来解决问题,因此这里就不能直接用树的层次序遍历的办法。因为按照那个办法,我们可以得到一层的节点,然后再把下一层的放到另外一个列表中。因此,我们需要考虑一下利用问题里提供的其他条件。
问题中还有几个额外的条件,就是我们可以假设整棵树是完美二叉树。也就是说,除了叶节点,其余每个节点都有两个子节点。 如果我们需要层次序的去遍历这颗二叉树的话,肯定首先要从根节点开始。它作为当前层的节点。而要能够继续遍历下一层,我们需要在当前节点的下一层节点,也就是当前层第一个节点的左子节点作为下一层的节点。这样我们才能遍历完一层后继续遍历下一层。
在上述的这个循环里,我们退出的条件就是当前节点的左子节点为空。这个时候意味着我们已经到了叶节点这一层了。
而在每一层的循环中,我们要将当前节点的左子节点的next指向它的右子节点。同时还有一个值得注意的地方,就是当它还有下一个节点,也就是它的next引用指向的节点不为空的情况下,它的右子节点的next要指向它的next元素的左子节点。这样一直到它的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) { if(root == null) return; TreeLinkNode curLevel = root, nextLevel = root.left; while(curLevel.left != null) { curLevel.left.next = curLevel.right; if(curLevel.next != null) { curLevel.right.next = curLevel.next.left; curLevel = curLevel.next; } else { curLevel.right.next = null; curLevel = nextLevel; nextLevel = curLevel.left; } } } }
这里问题的思路没有直接硬套树的层次遍历解决的套路,因为我们可以利用一些额外的条件,可以让整个问题的解法空间消耗更低。 而这里问题能够得到顺利解决的关键是任何一个非叶节点的元素都有左右两个子节点。
相关推荐
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题: ...
LeetCode::laptop:LeetCode解决方案
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
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 :keyboard:我的 Leetcode 解题答案
蓄水池算法 leetcode leetcode Post: 《双指针的魅力》 《常见面试题思想方法整理》 ...populating-next-right-pointers-in-each-node-ii: 二级指针代码虽然简洁优雅,但是对性能有影响,不如一级指针加if else判断快。
leetcode 2 和 c 一个让你谦卑的错误,胜过让你傲慢的成就。 leetcode 解决方案 :construction: 我的 Leetcode 算法问题练习解决方案使用 C#(.Net Core)并使用 MSUnit 进行测试。 希望它可以帮助任何人进行技术...
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
: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 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
leetcode:leetcode刷题
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。