题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。
注意：

需要返回双向链表最左侧的节点。

golang 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var pre *TreeNode
func convert(root *TreeNode) *TreeNode {
    midorder(root)
    for root != nil && root.Left != nil {
        root = root.Left
    }
    return root
}

func midorder(root *TreeNode) {
    if root == nil {
        return
    }

    midorder(root.Left)

    //前一个节点是现在节点的左子树，现在节点是前一个节点的右子树
    root.Left = pre
    if pre != nil {
        pre.Right = root
    }
    pre = root

    midorder(root.Right)
}