第 36 題：二叉搜索樹與雙向鏈表（典型遞歸問題）
傳送門：二叉搜索樹與雙向鏈表，爬盗伲客網(wǎng) online judge 地址胞锰。
輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表兢榨。
要求不能創(chuàng)建任何新的結(jié)點嗅榕，只能調(diào)整樹中結(jié)點指針的指向。
注意：
- 需要返回雙向鏈表最左側(cè)的節(jié)點吵聪。
例如凌那，輸入下圖中左邊的二叉搜索樹，則輸出右邊的排序雙向鏈表吟逝。
《劍指 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):
"""
返回雙向鏈表的兩端
"""
# 如果這個結(jié)點是葉子結(jié)點
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) { // 對應(yīng)剛開始的時候
linkedListTail = root;
// 在最左邊的地方記錄需要返回的雙向鏈表的根結(jié)點
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;
// 最后返回最左邊的結(jié)點
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;
// 在最左邊的地方記錄需要返回的雙向鏈表的根結(jié)點
res = root;
} else {
linkedListTail.right = root;
root.left = linkedListTail;
linkedListTail = root;
}
convert(root.right);
}
}
參考資料：https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5
