题解 | #二叉搜索树与双向链表#

package main

import (
	. "nc_tools"
)

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 *
 * @param pRootOfTree TreeNode类
 * @return TreeNode类
 */
func Convert( pRootOfTree *TreeNode ) *TreeNode {
    // write code here
    // 中序遍历
    if pRootOfTree == nil {
        return nil 
    }
    dummy := &TreeNode{}
    prev := dummy
    var inorderConvert func(node *TreeNode)
    inorderConvert = func(node *TreeNode){
        if node == nil {
            return
        }
        // 因为每次都是先向Left进行遍历，因此prev为left 比如6left为4
        inorderConvert(node.Left)
        prev.Right = node
        node.Left = prev
        prev = node
        inorderConvert(node.Right)
    }
    inorderConvert(pRootOfTree)
    head := dummy.Right
    head.Left = nil 
    return head
}