力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
面试题 17.12. BiNode
https://leetcode-cn.com/problems/binode-lcci/
题目描述
1
二叉树数据结构TreeNode可用来表示单向链表(其中left置空,right为下一个链表节点)。实现一个方法,把二叉搜索树转换为单向链表,要求依然符合二叉搜索树的性质,转换操作应是原址的,也就是在原始的二叉搜索树上直接修改。
2
3
返回转换后的单向链表的头节点。
4
5
注意:本题相对原题稍作改动
6
7
8
9
示例:
10
11
输入: [4,2,5,1,3,null,6,0]
12
输出: [0,null,1,null,2,null,3,null,4,null,5,null,6]
13
提示:
14
15
节点数量不会超过 100000。
Copied!
前置知识
二叉查找树
递归
二叉树的遍历
公司
暂无
思路
实际上这就是一个考察二叉树遍历 + 二叉搜索(查找)树性质的题目。这类题目特别需要注意的是指针操作,这一点和
链表反转系列
题目是一样的。
首先我们要知道一个性质:
对于一个二叉查找树来说,其中序遍历结果是一个有序数组
。 而题目要求你输出的恰好就是有序数组(虽然没有明说, 不过从测试用例也可以看出)。
因此一个思路就是中序遍历, 边遍历边改变指针即可。 这里有两个注意点:
1.
指针操作小心互相引用,导致死循环。
2.
你需要返回的是最左下角的节点,而不是题目给的 root。
3.
对于第一个问题, 其实只要注意操作指针的顺序,以及在必要的时候重置指针即可。
4.
对于第二个问题,我用了一个黑科技,让代码看起来简洁又高效。如果不懂的话, 你也可以换个朴素的写法。
理解了上面的内容的话, 那让我们进入正题。
其中绿色是我们要增加的连线,而黑色是是原本的连线。
我们再来看一个复杂一点的:
实际上,不管多么复杂。 我们只需要进行一次
中序遍历
,同时记录前驱节点。然后修改前驱节点和当前节点的指针即可,整个过程就好像是链表反转。
核心代码(假设 pre 我们已经正确计算出了):
1
cur
.
left
=
None
2
pre
.
right
=
cur
3
pre
=
cur
Copied!
剩下的就是如何计算 pre,这个也不难,直接看代码:
1
self
.
pre
=
None
2
def
dfs
(
root
):
3
dfs
(
root
.
left
)
4
# 上面的指针改变逻辑写到这里
5
self
.
pre
=
root
6
dfs
(
root
.
right
)
Copied!
问题得以解决。
这里还有最后一个问题就是返回值,题目要返回的实际上是最左下角的值。如何取到最左下角的节点呢?我们来看下核心代码你就懂了,代码比较简单。
1
self
.
pre
=
self
.
ans
=
None
2
def
dfs
(
root
):
3
if
not
root
:
return
4
dfs
(
root
.
left
)
5
root
.
left
=
None
6
if
self
.
pre
:
self
.
pre
.
right
=
root
7
# 当第一次执行到下面这一行代码,恰好是在最左下角,此时 self.pre = None,其他任何时候 self.pre 都不是 None。
8
if
self
.
pre
is
None
:
self
.
ans
=
root
9
self
.
pre
=
root
10
dfs
(
root
.
right
)
Copied!
关键点
指针操作
返回值的处理
代码
1
class
Solution
:
2
def
convertBiNode
(
self
,
root
:
TreeNode
)
->
TreeNode
:
3
self
.
pre
=
self
.
ans
=
None
4
def
dfs
(
root
):
5
if
not
root
:
return
6
dfs
(
root
.
left
)
7
root
.
left
=
None
8
if
self
.
pre
:
self
.
pre
.
right
=
root
9
if
self
.
pre
is
None
:
self
.
ans
=
root
10
self
.
pre
=
root
11
12
dfs
(
root
.
right
)
13
dfs
(
root
)
14
return
self
.
ans
Copied!
复杂度分析
时间复杂度:$O(N)$,其中 N 为树的节点总数。
空间复杂度:$O(h)$,其中 h 为树的高度。
相关题目
206.reverse-linked-list
92.reverse-linked-list-ii
25.reverse-nodes-in-k-groups-cn
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:
https://github.com/azl397985856/leetcode
。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
以前
第四章 - 高频考题(简单)
下一个
0001. 两数之和
最近更新
1yr ago
复制链接
内容
题目描述
前置知识
公司
思路
关键点
代码
相关题目