思路
纯纯的中序遍历而已,要求返回最小的节点不是说返回val最小的节点,而是说返回最左的节点,无语了,害得我调试了十分钟
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public:
vector<Node*> a;
void dfs(Node* p)
{
if(!p)return;
dfs(p->left);
a.push_back(p);
dfs(p->right);
}
Node* treeToDoublyList(Node* root) {
if(!root)return root;
dfs(root);
for(int i=0;i<a.size()-1;i++)
{
a[i]->right=a[i+1];
a[i+1]->left=a[i];
}
a[0]->left=a[a.size()-1];
a[a.size()-1]->right=a[0];
return a[0];
}
};