36. 二叉搜索树与双向链表

题目链接

牛客 (opens new window)

力扣 (opens new window)

题目描述

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

解题思路

package main

import "fmt"

//将BST转化为双向循环链表，不允许新建节点
//为防止歧义，左指针表示双链表向前指，右指针表示双链表向后指
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var pre *TreeNode //必须在全局变量上才可以实现

func treeToDoublyList(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	helper(root)
	head, tail := root, root
	for head.Left != nil {
		head = head.Left
	}
	for tail.Right != nil {
		tail = tail.Right
	}
	head.Left = tail
	tail.Right = head
	return head
}

func helper(root *TreeNode) {
	if root == nil {
		return
	}
	helper(root.Left)
	if pre != nil {
		root.Left = pre
		pre.Right = root
	}
	pre = root
	helper(root.Right)
}

func main() {
	root := &TreeNode{4, nil, nil}
	node1 := &TreeNode{2, nil, nil}
	node2 := &TreeNode{5, nil, nil}
	node3 := &TreeNode{1, nil, nil}
	node4 := &TreeNode{3, nil, nil}
	root.Left = node1
	root.Right = node2
	node1.Left = node3
	node1.Right = node4
	head := treeToDoublyList(root)
	tail := head.Left
	//从头开始遍历
	for i := 0; i <= 9; i++ {
		fmt.Printf("%d\t", head.Val)
		head = head.Right
	}
	//从尾开始遍历
	for i := 0; i <= 9; i++ {
		fmt.Printf("%d\t", tail.Val)
		tail = tail.Left
	}

}

当然，为了方便，也可以直接将pre作为引用变量传进来（它本身就是引用，弄个双重指针就欧克）

之前一直觉得多重指针没用，现在看来，真香~~~

func treeToDoublyList(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	var pre *TreeNode
	helper(root, &pre)//使用多重指针即可
	head, tail := root, root
	for head.Left != nil {
		head = head.Left
	}
	for tail.Right != nil {
		tail = tail.Right
	}
	head.Left = tail
	tail.Right = head
	return head
}

func helper(root *TreeNode, pre **TreeNode) {
	if root == nil {
		return
	}
	helper(root.Left, pre)
	if (*pre) != nil {
		root.Left = (*pre)
		(*pre).Right = root
	}
	(*pre) = root
	helper(root.Right, pre)
}