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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	//让左指针指向前面，右指针指向后面；
	//如果采用中序遍历，节点的处理是一个一个进行的，节点的插入位置是不同的，得取决于其父节点是其父父节点的左/右子树；
	//如果采用分治算法，对左子树、根节点、右子树进行连接即可，再返回开头节点
	//采用的是中序遍历
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree == nullptr) return nullptr;

		return dp(pRootOfTree);
    }

	TreeNode* dp(TreeNode* node){
		if(!node->left && !node->right){
			return node;  //单节点直接返回
		}

		TreeNode* node_1;  //不在if()中声明，可能出现未声明的情况，编译出错不允许
		TreeNode *node_2;
		if(node->left){
			node_1 = dp(node->left);  //左子节点的第一个节点

			TreeNode* curr= node_1;
			while(curr->right){
				curr = curr->right;
			}
			curr->right = node;
			node->left = curr;
		}

		if(node->right){
			node_2 = dp(node->right);  //右子节点的第一个节点

			node->right = node_2;
			node_2->left = node; 
		}

		return node->left? node_1: node;
	}
};