首页 > 试题广场 >

填充每个节点指向最右节点的next指针 ii

[编程题]填充每个节点指向最右节点的next指针 ii
  • 热度指数：16201 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
继续思考"填充每个节点指向最右节点的next指针" 这道题
如果给定的树可以是任意的二叉树呢?你之前的给出的算法还有效吗?
注意：
  • 你只能使用常量的额外内存空间
例如：
给出的二叉树如下：

调用完你给出的函数之后，这棵树应该变成：



说明：本题目包含复杂数据结构TreeLinkNode，点此查看相关信息
算法知识视频讲解
开通博客
头像 一叶浮尘
发表于 2020-04-04 17:00:58
继续思考"Populating Next Right Pointers in Each Node".这道题如果给定的树可以是任意的二叉树呢?你之前的给出的算法还有效吗?注意：你只能使用常量的额外内存空间层次遍历方法简单修改之后就能解决这道题目。改写之前的递归做法应该也能解决问题。 层次遍历也完全不 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 华科不平凡
发表于 2020-08-21 17:42:36
题目要求空间复杂度为常数级别，因此不能用递归或者使用队列辅助。 如果当前层中节点的next指针已经填充完毕，那么我们很容易根据当前层去填充下一层，只需要“记住”下一层的最左侧节点，即可通过循环实现题目的目标。在这里引入哑节点记录下一层最左侧节点。 另外的话，由于题中二叉树不是满二叉树或者完全二叉树， 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 我是嫩叠
发表于 2024-10-01 21:19:09
/** * Definition for binary tree with next pointer. * struct TreeLinkNode { * int val; * TreeLinkNode *left, *right, *next; * TreeLinkNode(int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 O-Precedence
发表于 2021-09-08 12:46:55
import java.util.*; public class Solution { public void connect(TreeLinkNode root) { if(root==null) return ; Queue< 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客448599388号
发表于 2021-02-08 10:01:47
如果是常量级空间复杂度 但我看通过答案 使用的变量都与树的高度有关系 这也算常量级的么
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树
难度：
97条回答 27609浏览

热门推荐

通过挑战的用户

查看代码

相关试题

填充每个节点指向最右节点的next指针 ii

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号