题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
http://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
/*
struct TreeNode {
int val;
struct TreeNode left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};/
class Solution {
public:
map<int, TreeNode> m;
vector<int> v;
void bianli(TreeNode</int> root){
if(!root) return;
bianli(root->left);
m[root->val] = root;
v.push_back(root->val);
bianli(root->right);
return;
}
TreeNode* Convert(TreeNode* pRootOfTree) {
if(!pRootOfTree) return {};
bianli(pRootOfTree);
m[v[0]]->right = m[v[1]];
m[v[v.size()-1]]->left = m[v[v.size()-2]];
for(int i=1;i<v.size()-1;i++){
m[v[i]]->left = m[v[i-1]];
m[v[i]]->right = m[v[i+1]];
}
return m[v[0]];
}
};
