第 36 题：二叉搜索树与双向链表（典型递归问题）
传送门：二叉搜索树与双向链表，牛客网 online judge 地址。
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。
注意：
- 需要返回双向链表最左侧的节点。
例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。
《剑指 Offer （第 2 版）》第 36 题：二叉搜索树与双向链表（典型递归问题）-1
思路：
《剑指 Offer （第 2 版）》第 36 题：二叉搜索树与双向链表（典型递归问题）-2
分析：参考解答有一定价值，要好好研究一下。画图就清楚解法了。
Python 代码：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def convert(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root is None:
return None
head, _ = self.__dfs(root)
return head
def __dfs(self, root):
"""
返回双向链表的两端
"""
# 如果这个结点是叶子结点
if root.left is None and root.right is None:
return (root, root)
# 如果有左孩子，还有右边孩子
if root.left and root.right:
ll, lr = self.__dfs(root.left)
rl, rr = self.__dfs(root.right)
# 下面穿针引线
lr.right = root
root.left = lr
root.right = rl
rl.left = root
return (ll, rr)
# 走到这里，就是二者之一为空
if root.left:
ll, lr = self.__dfs(root.left)
lr.right = root
root.left = lr
return (ll, root)
if root.right:
rl, rr = self.__dfs(root.right)
root.right = rl
rl.left = root
return (root, rr)
C++ 代码：返回一个 pair
《剑指 Offer （第 2 版）》第 36 题：二叉搜索树与双向链表（典型递归问题）-3
Java 代码：
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
private TreeNode linkedListTail;
private TreeNode res;
public TreeNode Convert(TreeNode pRootOfTree) {
convert(pRootOfTree);
return res;
}
/**
* 中序遍历
*
* @param root
*/
private void convert(TreeNode root) {
if (root == null) {
return;
}
convert(root.left);
// 中序遍历真正做事情的地方
if (linkedListTail == null) { // 对应刚开始的时候
linkedListTail = root;
// 在最左边的地方记录需要返回的双向链表的根结点
res = root;
} else {
linkedListTail.right = root;
root.left = linkedListTail;
linkedListTail = root;
}
convert(root.right);
}
}
Python 代码：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def __init__(self):
self.linked_list_tail = None
self.res = None
def convert(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
self.__dfs(root)
return self.res
# 中序遍历
def __dfs(self, root):
if root is None:
return
self.__dfs(root.left)
if self.linked_list_tail is None:
self.linked_list_tail = root
self.res = root
else:
self.linked_list_tail.right = root
root.left = self.linked_list_tail
self.linked_list_tail = root
self.__dfs(root.right)
Java 代码：分治算法
public class Solution2 {
public TreeNode convert(TreeNode root) {
if (root == null) {
return root;
}
TreeNode left = rightMost(root.left);
TreeNode right = leftMost(root.right);
convert(root.left);
convert(root.right);
if (left != null) {
left.right = root;
}
root.left = left;
if (right != null) {
right.left = root;
}
root.right = right;
// 最后返回最左边的结点
while (root.left != null) {
root = root.left;
}
return root;
}
TreeNode leftMost(TreeNode root) {
if (root == null) {
return null;
}
while (root.left != null) {
root = root.left;
}
return root;
}
TreeNode rightMost(TreeNode root) {
if (root == null) {
return null;
}
while (root.right != null) {
root = root.right;
}
return root;
}
}
C++ 代码：
class Solution {
public:
TreeNode* convert(TreeNode* root) {
if (!root) return root;
stack<TreeNode*> st;
while (root){
st.push(root);
root = root->left;
}
TreeNode* ans = st.top();
TreeNode* last = NULL;
while (!st.empty()){
TreeNode* tmp = st.top();
st.pop();
if (!last) last = tmp;
else {
last->right = tmp;
tmp->left = last;
last = tmp;
}
tmp = tmp->right;
while (tmp){
st.push(tmp);
tmp = tmp->left;
}
}
return ans;
}
};
Java 代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode convert(TreeNode root) {
if (root == null) return null;
TreeNode dummy = new TreeNode(-1);
TreeNode pre = dummy;
Stack<TreeNode> stack = new Stack<>();
while (root != null || stack.size() != 0){
while (root != null){
stack.push(root);
root = root.left;
}
if (stack.size() != 0){
TreeNode node = stack.pop();
pre.right = node;
node.left = pre;
pre = pre.right;
root = node.right;
}
}
dummy.right.left = null;
dummy = dummy.right;
return dummy;
}
}
Java 代码：
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
private TreeNode linkedListTail;
private TreeNode res;
public TreeNode Convert(TreeNode pRootOfTree) {
convert(pRootOfTree);
return res;
}
/**
* 中序遍历
*
* @param root
*/
private void convert(TreeNode root) {
if (root == null) {
return;
}
convert(root.left);
// 中序遍历真正做事情的地方
if (linkedListTail == null) {
linkedListTail = root;
// 在最左边的地方记录需要返回的双向链表的根结点
res = root;
} else {
linkedListTail.right = root;
root.left = linkedListTail;
linkedListTail = root;
}
convert(root.right);
}
}
参考资料：https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5
