二叉搜索树与双向链表

1. 题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

2. 思路

• 中序遍历
• 递归 跟二叉树展开为链表.md不同，这道题是中序遍历并且是排序的双向链表，而那道题是先序遍历

3. 实现

3.1. 中序遍历

package main

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

/**
 *
 * @param pRootOfTree TreeNode类
 * @return TreeNode类
 */
//时间：O(N)
//空间：O(N)
func Convert(pRootOfTree *TreeNode) *TreeNode {
	if pRootOfTree == nil {
		return nil
	}

	nodes := make([]*TreeNode, 0)
	midOrdered(pRootOfTree, &nodes)

	for i := 0; i < len(nodes)-1; i++ {
		nodes[i].Right = nodes[i+1]
		nodes[i+1].Left = nodes[i]
	}
	nodes[0].Left = nil
	nodes[len(nodes)-1].Right = nil

	return nodes[0]
}

func midOrdered(node *TreeNode, nodes *[]*TreeNode) {
	if node == nil {
		return
	}

	midOrdered(node.Left, nodes)
	*nodes = append(*nodes, node)
	midOrdered(node.Right, nodes)
}

3.2. 递归

func Convert2(pRootOfTree *TreeNode) *TreeNode {
	if pRootOfTree == nil {
		return nil
	}

	leftNode := Convert2(pRootOfTree.Left)
	rightNode := Convert2(pRootOfTree.Right)

	//左子树需要转换一下，找到最右边的节点
	//右子树不需要，因为需要的就是最左边的节点
	retNode := leftNode
	if leftNode != nil {
		leftNode = findRight(leftNode)
	} else {
		retNode = pRootOfTree
	}

	//父亲连接到左右子树
	pRootOfTree.Left = leftNode
	pRootOfTree.Right = rightNode

	//左右子树链接到父亲
	if leftNode != nil {
		leftNode.Right = pRootOfTree
	}
	if rightNode != nil {
		rightNode.Left = pRootOfTree
	}
	return retNode

}

func findRight(node *TreeNode) *TreeNode {
	for node.Right != nil {
		node = node.Right
	}
	return node
}

4. 参考

• 二叉搜索树与双向链表_牛客题霸_牛客网