剑指offer No.26 二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
比如将二元查找树 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。
首先，我们知道：在二叉树中，每个结点都有两个指向子结点的指针。在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。
其次，由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每一个结点，这是因为中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每一个结点。
最后，按照中序遍历的顺序，当我们遍历转换到根结点（值为10的结点）时，它的左子树已经转换成一个排序的链表了，并且处在链表中的最后一个结点是当前值最大的结点。我们把值为8的结点和根结点链接起来，此时链表中的最后一个结点就是10了。接着我们去遍历转换右子树，并把根结点和右子树中最小的结点链接起来。
很明显，转换它的左子树和右子树，由于遍历和转换过程是一样的，很自然地想到可以用递归。
写递归程序最重要的是弄明白递归进入的条件、递归返回的状态，如果递归进入时改变了环境，返回时应当恢复环境，就像栈的操作一样
使用指针变量时，要记得初始化
该算法没有返回链表头，而是返回了root。
1、C++
//
// Created by jiangxingqi on 2019/4/20.
//
#include <iostream>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
// lastNode指向双向链表的尾结点
TreeNode* lastNode =NULL;
TreeNode* headNode=ConvertNode(pRootOfTree, lastNode);
// headNode指向根节点root，往左移动到链表的头结点
while (headNode != NULL && headNode->left != NULL) {
headNode = headNode->left;
}
return headNode;
}
// 该算法没有返回链表头，而是返回了root
TreeNode* ConvertNode(TreeNode* rootTree, TreeNode* lastNode) {
if (rootTree == NULL) {
return NULL;
}
// 转换左子树
if (rootTree->left != NULL) {
lastNode=ConvertNode(rootTree->left, lastNode);
}
// 与根节点的衔接
rootTree->left = lastNode;
if (lastNode != NULL) {
lastNode->right = rootTree;
}
lastNode = rootTree;
// 转换右子树
if (rootTree->right != NULL) {
lastNode=ConvertNode(rootTree->right, lastNode);
}
return lastNode;
}
};2、Java
package offer.convert;
public class Solution {
public static TreeNode Convert(TreeNode pRootOfTree) {
TreeNode lastNode =null;
TreeNode headNode=ConvertNode(pRootOfTree, lastNode);
while (headNode != null && headNode.left != null) {
headNode = headNode.left;
}
return headNode;
}
public static TreeNode ConvertNode(TreeNode rootTree, TreeNode lastNode) {
if (rootTree == null) {
return null;
}
if (rootTree.left != null) {
lastNode=ConvertNode(rootTree.left, lastNode);
}
rootTree.left = lastNode;
if (lastNode != null) {
lastNode.right = rootTree;
}
lastNode = rootTree;
if (rootTree.right != null) {
lastNode=ConvertNode(rootTree.right, lastNode);
}
return lastNode;
}
}