题解 | 二叉搜索树与双向链表

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Solution {
  private:
    vector<int> ans;
	TreeNode* prev_ptr=nullptr;
	TreeNode* start_head=nullptr;
	TreeNode* end_head=nullptr;
  public:
    void visit(TreeNode* node) {
        if (node == nullptr)return;
        visit(node->left);
        ans.push_back(node->val);
		node->left = prev_ptr;
		prev_ptr = node;
		if(start_head==nullptr){
			start_head = node;
		}
		end_head=node;
        visit(node->right);
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        visit(pRootOfTree);
		TreeNode* next =nullptr;
		TreeNode* cur = end_head;
		while(cur!=nullptr){
			cur -> right = next;
			next = cur;
			cur = cur->left;
		}
		return start_head;
    }
};

每次遍历到中序时候记录下，当到下一个中序的时候调整left为上一个中序的节点。然后不断重复。直到最后一个节点完成。此时left已经建立起来了，但是right并没有设置，而此时正好节点在left方向的最后一个节点，我们从过left向前遍历，同时设置right节点，遇到空代表设置完毕了。