题解 | JZ36 二叉搜索树与双向链表
这道题是把一个二叉搜索树转换成一个双向链表。
我们知道一个二叉搜索树按照中序遍历，的出来的结果是一个排好序的升序序列。而我们要实现的双向链表也是一个升序的双向链表。
因此，我们可以考虑一个中序遍历的递归进行。
我们首先想能否直接递归用Convert()函数实现整个算法。
假设Convert()的作用就是给定一个二叉搜索树的入口结点，返回一个双向链表的最小值的指针。
我们第一步要考虑它和左右子节点之间的关系，如何递归下去？
假设我们已经完成了Convert(pRootOfTree->left)，即把pRootOfTree的左子节点已经变成了一个双向链表，返回得到的是最小值的指针。而对于我们来说，这个返回的指针并没有作用，因为pRootOfTree并不是和这个最小值指针相接。
所以我们需要一个变量记录出这个要和pRootOfTree相连的指针。
我们可以知道在中序遍历中，右子树是最后遍历的。而和pRootOfTree左边相连的就是pRootOfTree左子树的最右的叶子节点。因此，我们只需要对叶子结点赋值给一个pre指针就可以在pRootOfTree的左子树退出递归回到pRootOfTree这一层得到，pRootOfTree的左边的结点。
这样我们就完成了和pRootOfTree和左边的相连。
而右边的怎么和左边的相连呢？
如果我们只递归到叶子结点，那么我们只能完成叶子结点和它上一层结点的相连。
基于这一点的考虑，所以我们不能只递归到叶子节点。因此需要递归到叶子结点的下一层，空结点才能完成pRootOfTree结点和右子树的最左叶子结点的连接。（这算一个trick，不考虑到这一点是没法用一个函数递归完成整个操作的）
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* pre;
TreeNode* root;
TreeNode* Convert(TreeNode* pRootOfTree) {
if (!pRootOfTree) return nullptr;
Convert(pRootOfTree->left);
if (!root) root = pRootOfTree;
if (pre) {
pRootOfTree->left = pre;
pre->right = pRootOfTree;
}
pre = pRootOfTree;
Convert(pRootOfTree->right);
return root;
}
};
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
#
# @param pRootOfTree TreeNode类
# @return TreeNode类
#
class Solution:
root = None
pre = None
def Convert(self , pRootOfTree ):
# write code here
if pRootOfTree is None:
return None
self.Convert(pRootOfTree.left)
if self.root is None:
self.root = pRootOfTree
if self.pre:
self.pre.right = pRootOfTree
pRootOfTree.left = self.pre
self.pre = pRootOfTree
self.Convert(pRootOfTree.right)
return self.root
腾讯HR面2077人在聊
