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

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
    }

    // 中序遍历二叉搜索树得到递增序列
    // 需要使用 prev 记录前一个遍历的指针
    var prev *TreeNode
    var inorder func(root *TreeNode) 
    inorder = func(root *TreeNode) {
        if root == nil {
            return
        }
	
        inorder(root.Left)
	  	// 更新当前节点的前驱
        root.Left = prev
	  	// 如果 prev 不为 nil，将前驱后继指向当前节点
        if prev != nil {
            prev.Right = root
        }
	  	// 更新当前节点为中序遍历的前驱节点
        prev = root

        inorder(root.Right)
    }

    inorder(pRootOfTree)
	// 双向链表的头结点是树中的最左侧节点
    for pRootOfTree.Left != nil {
        pRootOfTree = pRootOfTree.Left
    }
    
    return pRootOfTree
}