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
拿到该题的第一反应是层次遍历,对每一层的节点进行链接,但是看到提示说需要常量空间。因此就尝试别的方法,已知,将亲兄弟节点进行链接是很容易的。每层的断裂带是堂兄弟,但是每一对堂兄弟的父节点都是亲兄弟,因此,可以得到这样的结论,根据断裂的堂兄弟的父节点(假设全部亲兄弟节点已经完成链接)可以将两个堂兄弟链接起来,比如说图中的5 、6是断裂的,但是我们可以在遍历到第二层时,可以根据2 3 提前(或滞后)将5 6 先关联起来。代码如下
public void connect(TreeLinkNode root) {
linkLeft2Right(root);
TreeLinkNode left = root;
while (left != null) {
linkRight2left(left);
left = left.left;
}
}
private void linkLeft2Right(TreeLinkNode root) {
if (root != null && root.left != null) {
root.left.next = root.right;
}else{
return;
}
linkLeft2Right(root.left);
linkLeft2Right(root.right);
}
private void linkRight2left(TreeLinkNode root) {
TreeLinkNode node = root;
while (node.next != null) {
if(node.next.left !=null && node.right != null){
node.right.next = node.next.left;
}
node = node.next;
}
}
分享到:
相关推荐
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题库 pyshua Python 算法题练习 用法: python Judge.py library problem 例子: python Judge.py leetcode TwoSum 如何贡献: 收录题库 LeetCode (还有4题未录入, 分别为 LRU Cache, Copy List with Random ...
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...
Populating Next Right Pointers in Each Node II 二叉树的构建 Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from Inorder and Postorder Traversal 二叉查找树 Unique ...
LeetCode题目Largest Rectangle in Histogram 解答
leetcode-pp-node 官网后端。 使用 koa2 结合 Github Actions 开发。目前采用静态 JSON 存放题解,讲义,用户信息等数据,后期使用数据库承载内容。 TODOS 在 91 网站直接提交代码到力扣中,获取执行结果并在 91 中...
LeetCode 解决VS Code中的LeetCode问题 英文文件| 文件 :exclamation_mark: 注意 :exclamation_mark: -登录LeetCode端点的解决方法注意:如果使用的是leetcode-cn.com ,则可以忽略此部分。 最近,我们发现。 此问题...
[117]填充每个节点的下一个右侧节点指针 II|populating-next-right-pointers-in-each-node-ii给定一个二叉树填充
leetcode 两分球-2 问题1 () 问题2 () 问题3 ()
leetcode 两分球-1 问题1 () 问题2 () 问题3 ()
一:题意: 删除一颗二叉搜索树的一个节点。 二:思路 二叉搜索树的结点删除比插入较为复杂,总体来说,结点的删除可归结为三种情况: 1、 如果结点z没有孩子... def deleteNode(self, root, key): def postOrder(r
450._Delete_Node_in_a_BST【LeetCode单题讲解系列】
lru cache leetcode leetcode 记录自己刷leetcode时遇到的一些值得记下来的题目, 分为一些子项 bytedance ...populating-next-right-pointers-in-each-node sum-root-to-leaf-numbers best-time-to-buy
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode 答案解析 golang解答
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
Array题型_双指针Two_Pointers套路【LeetCode刷题套路教程2】
蓄水池算法 leetcode leetcode Post: 《双指针的魅力》 《常见面试题思想方法整理》 ...populating-next-right-pointers-in-each-node-ii: 二级指针代码虽然简洁优雅,但是对性能有影响,不如一级指针加if else判断快。
四平方和定理 leetcode Leetcode practice Table of content Tree 92.reverse-linked-list-ii (反转链表 ...94.binary-tree-inorder-...116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点
leetcode中文版