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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
1. 二叉搜索树的特点：左节点值 < 根节点值 < 右节点值；由此可知，大体思路是使用中序遍历；
2. 又由于需要返回头节点，由此可知遍历到左节点尽头时，第一开始根处理时所在的节点即为头节点，并且此时的pre为nullptr，若pre不为nullptr，则必然出现pre->right指向当前节点的现象；
3. 处理完pre之后，就来到了当前节点如何指向上一个节点pre以及pre如何移动到下一个的问题；故出现：
	cur->left = pre;
	pre = cur;
	的代码；
4. 之后，就是遍历处理右边的节点，递归处理；

	}
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if (pRootOfTree == nullptr)
					return nullptr;
				
				BstToLink(pRootOfTree);

				pre_->right = nullptr;

				return head_;
    }

		void BstToLink(TreeNode* node) {
			if (node == nullptr)
				return;

			BstToLink(node->left);

			if (pre_ == nullptr) {
				head_ = node;
			} else {
				pre_->right = node;
			}

			node->left = pre_;
			pre_ = node;

			BstToLink(node->right);
		}

private:
	TreeNode* head_ {nullptr};
	TreeNode* pre_ {nullptr};
};