- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/
给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL
。
初始状态下,所有 next 指针都被设置为 NULL
。
示例:
输入:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
输出:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。
提示:
1、 你只能使用常量级额外空间;
2、 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度;
把一棵完全二叉树的每层节点之间顺序连接,形成单链表。
树的问题一般都可以用递归解决。这个题中,同样可以使用dfs解决。
注意题目已经声明了是完全二叉树,从根节点开始找到任意节点,将其左孩子指向右孩子。如果该节点已经指向了同层的其他节点,说明需要连接两个子树,比如例子中的2->3
,那么不仅要把2的左孩子4指向右孩子5,还要把2的右孩子5指向2的next节点的左孩子6。这样递归完成了,每层就是单链表了。
发现一篇文章讲得很细:http://www.cnblogs.com/yrbbest/p/4437341.html
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if not root: return
if root.right:
root.left.next = root.right
if root.next:
root.right.next = root.next.left
self.connect(root.left)
self.connect(root.right)
return root
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我有一个 Segment 类和一个这样的段数组: private static class Segment { int number, type; Segment(in
我在 SO 中看到一些创建 multilanguage websites in JavaScript 的好建议包括 this article on JavaScript internationaliz
我们有浏览器前缀或黑客 (for Google and Safari) text-align: -webkit-right; (for Firefox) text-align:
过去几天我一直在关注这个问题,我正处于需要寻求帮助的地步。 http://cub.northnodes.com/index.php/about/mission/ 我需要立即捐赠 列一直 float 到
When I press right ctrl, I want the right shift the text will align right. When I press left ctrl le
我已经将右侧的列拆分为顶部和底部。在每个部分中,我在执行以下操作时遇到问题:我希望顶部占据左列高度的 50%,底部占据左列高度的另外 50%。 +-------------------+-------
我知道这个问题的标题很糟糕。对不起。 我有四个 div similar to this .我想要做的只是让 div 编号 2 和 4 之间的垂直空间被删除,而不改变 HTML 的结构。是否可以仅使用
我将表格设置为 100% 宽度。我会添加一个带有 php 的随机 div,有时会充满广告。我希望广告 div 位于表格的右侧和内容。我希望表格位于左侧,但仍为 100% 左右,它将填充广告 div 左
这个问题在这里已经有了答案: Bootstrap align navbar items to the right (24 个答案) 关闭 5 年前。
.floatright { float: right;margin: 0 0 10px 10px;clear: right;width:60px; height:60px; } Lorem
我正在尝试将 td 中的某些内容右对齐。 align="right"有效,但 text-align:right 无效。这是一个 jsfiddle显示这两种情况的示例。除了右对齐右列外,这两种情况是相同
在设计网站时,您认为用于特定任务的最佳图像格式是什么? 在试图找出用于特定任务的格式时,我总是发现自己处于两难境地……例如,我应该全面使用 .jpg 吗?或者,我何时以及为什么应该使用 .png? 例
我是一个 MySQL 新手,今天我尝试设置一个超过 5 行的 MySQL 调用。我不断收到语法错误,我尝试修复了几个小时,但我不知道问题出在哪里。这是代码: USE myDatabase; DELIM
这让我发疯。我有一个 div float 到另一个 div 的右侧,如下所示: Current Membership: 我有以下 css 规则: div#container { f
我有以下代码片段,它会产生不需要的“填充”区域,而填充为零。如何避免这个区域? 代码 div.left { background-color: red; max-width: 25%; f
在 C++ 中,表达式 left() = right() 求值 right() left() 按那个顺序。 right() 先行,正如已讨论过的 here. 我想不出让 right() 先走的理由。你
我有一个很小的菜单列表,当鼠标靠近时它应该会增长。在其原始状态下,菜单是右对齐的,悬停时每第二个元素向右移动并左对齐以为增加的高度腾出空间(参见 JSFiddle )。 ul { font-siz
td.myclass{ width: 6em; text-align: right; padding-right: 2em; } 如您所见,我希望单元格中的文本右对齐,距离单元
你怎么能看到 http://jsfiddle.net/73wst/ 我想在停止下开始,但我不知道如何设置它的样式。 我的 HTML: Stop Start 我的 CSS: .sta
一个大的内部 div 在一个小的外部 div 中,并且外部 div 溢出自动。但是为什么没有内部 div margin-right 和外部 div padding-right? html
我是一名优秀的程序员,十分优秀!