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

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

获取左右子树双向链表，则只需要让当前根节点的左右指针指向左链表的最后一个节点，右指针指向右链表的第一个节点，并返回第一个节点

#include <cstddef>
#include <vector>
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
		if(pRootOfTree==nullptr) return nullptr;
		TreeNode* leftnode = Convert(pRootOfTree->left);
		TreeNode* rightnode = Convert(pRootOfTree->right);
		if(rightnode != nullptr){
			pRootOfTree->right = rightnode;
			rightnode->left = pRootOfTree;
		}
		if(leftnode != nullptr){
			while(leftnode->right!=nullptr){
				leftnode = leftnode->right;
			}
			pRootOfTree->left = leftnode;
			leftnode->right = pRootOfTree;
		}
		while(pRootOfTree->left != nullptr){
			pRootOfTree = pRootOfTree->left;
		}
		return pRootOfTree;
    }
};