题目
- 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
- 要求不能创建任何新的结点,只能调整树中结点指针的指向。
- 注意:
需要返回双向链表最左侧的节点。
示例
- 示例1
二叉树
10
/ \
6 14
/ \ / \
4 8 12 16
转换后的双向链表(LeetCode 里是双向循环链表)
4 <=> 6 <=> 8 <=> 10 <=> 12 <=> 14 <=> 16
代码
- DFS + 特判 视频讲解
class Solution {
public:
TreeNode* convert(TreeNode* root) {
if(!root) return NULL;
auto sides = dfs(root);
return sides.first;
}
pair<TreeNode*, TreeNode*> dfs(TreeNode* root){
if(!root->left && !root->right) return {root,root};
if(root->left && root->right){
// 递归遍历左右子树
auto lsides = dfs(root->left), rsides = dfs(root->right);
lsides.second->right = root, root->left = lsides.second;
root->right = rsides.first, rsides.first->left = root;
// 返回两端节点
return {lsides.first, rsides.second};
}
if(root->left){
// 递归遍历左子树
auto lsides = dfs(root->left);
lsides.second->right = root, root->left = lsides.second;
// 返回两端节点
return {lsides.first, root};
}
if(root->right){
// 递归遍历右子树
auto rsides = dfs(root->right);
root->right = rsides.first, rsides.first->left = root;
// 返回两端节点
return {root, rsides.second};
}
}
};
- DFS
// 二叉搜索树 中序遍历 递增
class Solution {
public:
TreeNode *pre = NULL, *head = NULL;
TreeNode* convert(TreeNode* root) {
if (!root) return NULL;
dfs(root);
// leetcode 是 循环链表, 要加上 这里
// 循环链表 首尾相连, pre 最后在 链表尾结点
//head->left = pre, pre->right = head;
return head;
}
void dfs(TreeNode* cur) { // 此处 用 cur 更贴切
if (!cur) return;
dfs(cur->left); // 中序遍历: 左中右
if (!pre) head = cur; // pre为NULL, 找到头结点
else { // 存在 pre, 将 pre 与 cur 左右 互连
pre->right = cur;
cur->left = pre;
}
pre = cur; // 更新 pre
dfs(cur->right);
}
};
两种方法都很强,俺受教了!先记下来慢慢看。
题目
:二叉搜索树与双向链表