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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <queue>
#include <vector>
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
		if(not pRootOfTree) return nullptr;

		std::queue<TreeNode*> q;
		TreeNode* newHead{};
		auto mid = [&q, &newHead](auto&& self, TreeNode* n) {
			if(not n) return;
		    self(self, n->left);
			q.push(n);
			if(q.size() == 2) [[likely]] {
				auto l = q.front(), r = q.back();
				l->right = r;
				r->left = l;
                q.pop();
			} else {
				newHead = n;
			}
			self(self, n->right);
		};
        mid(mid, pRootOfTree);
		return newHead;
    }
};