剑指offer-二叉搜索树与双向链表

一、题意

题目描述

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

二、分析

• 二叉排序树的每个节点均由两个指针指向其两个孩子，双向链表中每个节点又都有两个指针指向其前驱和后继

• 二叉排序树的左节点的值 < 根结点的值 < 右子节点的值，其中序遍历就是一个排序好的信息串

对应两种方法实现：

• 中序遍历来实现二叉搜索树向双向链表的转换，访问过程需修改为链接操作

• 把左子树和右子树都转换成排序的双向链表之后再和根节点链接起来，整棵二叉搜索树就转换成了排序的双向链表

中序遍历

中序遍历中当前结点的前一个节点：

• 要么是当前结点的左子树的的最右孩子
• 要么是当前结点其前一个节点的右孩子

三、代码实现(采用递归)

>folded main.go

package main

import (
	"fmt"
)

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

var tail *TreeNode = nil

// 中序遍历：左--中--右
func ConvertRecursion(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}

	// 如果左子树为空，则根结点root为双向链表的头结点
	head := ConvertRecursion(root.Left)
	if head == nil {
		head = root
	}

	// 连接当前结点root和当前链表的尾结点tail
	root.Left = tail
	if tail != nil {
		tail.Right = root
	}
	tail = root

	// 遍历当前结点的右子树
	ConvertRecursion(root.Right)

	return head
}

func main() {
	//     4
	//   3   5
	// 2
	node2 := &TreeNode{2, nil, nil}
	node3 := &TreeNode{3, node2, nil}
	node5 := &TreeNode{5, nil, nil}
	node4 := &TreeNode{4, node3, node5}
	head := ConvertRecursion(node4)
	for head != nil {
		fmt.Println()
		fmt.Printf("curval: %d", head.Val)
		head = head.Right
	}
	for tail != nil {
		fmt.Println()
		fmt.Printf("curval: %d", tail.Val)
		tail = tail.Left
	}
}

// 输出如下：
curval: 2
curval: 3
curval: 4
curval: 5
curval: 5
curval: 4
curval: 3
curval: 2

Process finished with exit code 0

四、总结与思考

• ConvertRecursion函数的功能。
  1、输入：输入一个二叉搜索树的根节点。
  2、过程：将其转化为一个有序的双向链表。
  3、输出：返回该链表的头节点。

• tail节点的作用
  1、用于记录当前链表的末尾节点。

• 递归过程
  1、按照中序遍历，将整个树分解成了无数的小树，然后将他们分别转化成一小段一小段的双向链表。再利用tail节点记录总的链表的末尾，然后将这些小段链表一个接一个地加到末尾。所以tail节点要定义成全局的。

参考
剑指Offer–027-二叉搜索树与双向链表