BiNode

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

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

示例：

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

示例代码1：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.head = self.cur = TreeNode(None)  # #定义头结点，最后返回头结点的右子节点

    def inOrder(self, root):
        if not root:
            return None

        self.inOrder(root.left)

        # 将节点依次插入新树的右侧，左侧均为None
        root.left = None  # #当前节点的左子节点置空
        self.cur.right = root  # #上个节点的右子节点赋值为当前节点
        self.cur = root  # #更新当前节点，注意顺序

        self.inOrder(root.right)

    def convertBiNode(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.inOrder(root)
        
        return self.head.right

解题思路：

看到二叉搜索树 -> 想到中序遍历，本题即是：

1. 创建一个新树，用来保存最后的节点头；
2. 中序遍历二叉搜索树，遍历的同时 将节点依次插入新树的右侧，左侧均为None
3. 返回新树的右节点

示例代码2：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def convertBiNode(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.pre = self.cur = None

        def dfs(root):
            if not root:
                return None
            dfs(root.left)
            
            root.left = None
            if self.pre:
                self.pre.right = root
            else:
                self.cur = root
            self.pre = root

            dfs(root.right)
        
        dfs(root)

        return self.cur

复杂度分析

• 时间复杂度：O(N)O(N)，其中 N 为树的节点总数。
• 空间复杂度：O(h)O(h)，其中 h 为树的高度。