LeetCode | 面试题 17.12. BiNode【Python】

落日映苍穹つ 2022-11-12 10:59 183阅读 0赞

## 问题 ##

[力扣][Link 1]

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意：本题相对原题稍作改动

**示例：**

输入： [4,2,5,1,3,null,6,0]
    输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]

**提示：**

*  节点数量不会超过 100000。

## 思路 ##

**DFS**

中序遍历

## 代码 ##

### Python3 ###

# Definition for a binary tree node.
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    
    class Solution:
        def convertBiNode(self, root: TreeNode) -> TreeNode:
            def dfs(root):
                pre = cur = root
                if root:
                    if root.left:
                        pre, cur = dfs(root.left)
                        # 左子树的下一个链表节点是当前root节点
                        cur.right = root
                        # 修改当前指针
                        cur = root
                        root.left = None
                    if root.right:
                        root.right, cur = dfs(root.right)
                return pre, cur
            
            return dfs(root)[0]

## 链接 ##

[GitHub][]

[Link 1]: https://leetcode-cn.com/problems/binode-lcci/
[GitHub]: https://github.com/Wonz5130/LeetCode-Solutions/tree/master/solutions/Interview-17.12-BiNode-LCCI

发表评论取消回复

表情：

评论列表（有 0 条评论，183人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetCode(力扣)面试题

1.两数求和（two sum）题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组...

电玩女神/ 2024年04月17日 05:38/ 0 赞/ 69 阅读

相关 hiho#1712 : 字符串排序

\1712 : 字符串排序时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述一般我们在对字符串排序时，都会按照字典序排序。当字符

布满荆棘的人生/ 2024年02月18日 19:10/ 0 赞/ 20 阅读

相关 leetcode面试题--压缩字符串

题目描述：字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有

灰太狼/ 2022年12月14日 13:51/ 0 赞/ 134 阅读

相关算法面试题汇总 leetcode

[算法面试题汇总 leetcode][leetcode] [leetcode]: https://leetcode-cn.com/leetbook/read/top-i

- 日理万妓/ 2022年12月10日 04:52/ 0 赞/ 196 阅读

相关 Leetcode 面试题URL化

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

亦凉/ 2022年10月31日 05:24/ 0 赞/ 134 阅读

相关 leetcode 面试题

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

我就是我/ 2022年09月02日 11:54/ 0 赞/ 211 阅读

相关 hihoCoder--#1712

\1712 : 字符串排序时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述一般我们在对字符串排序时，都会按照字典序排序。当字符

迈不过友情╰/ 2022年05月27日 09:59/ 0 赞/ 283 阅读

相关 hihoCoder1712

\1712 : 字符串排序时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述一般我们在对字符串排序时，都会按照字典序排序。

我不是女神ヾ/ 2022年01月10日 03:37/ 0 赞/ 222 阅读

相关 leetcode-top面试题打家劫舍

题目你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统

Love The Way You Lie/ 2021年11月22日 23:34/ 0 赞/ 243 阅读

相关 P1712 区间

题目描述在数轴上有 n个闭区间 [l1,r1],[l2,r2],…,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得...

你的名字/ 2021年03月25日 14:51/ 0 赞/ 483 阅读