AcWing 49. 二叉搜索树与双向链表
原题链接
中等
作者:
andream7
,
2020-12-26 11:00:54
,
所有人可见
,
阅读 420
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
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);
auto rsides = dfs(root->right);
lsides.second->right = root, root->left = lsides.second;
rsides.first->left = root, root->right = rsides.first;
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);
rsides.first->left = root, root->right = rsides.first;
return {root, rsides.second};
}
}
};