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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
TreeNode* head = nullptr;
TreeNode* pre = nullptr;//为什么不能两个在一行声明？
    TreeNode* Convert(TreeNode* pRootOfTree) {
        //按照提议不能使用栈
		//使用双指针
		if(pRootOfTree==nullptr) return nullptr;
		Convert(pRootOfTree->left);
		if(head==nullptr){
			head = pRootOfTree;
			pre = pRootOfTree;
		}
		else{
			pRootOfTree->left = pre;
			pre->right = pRootOfTree;
			pre = pRootOfTree;
		}
		Convert(pRootOfTree->right);
		return head;
    }
};

二叉搜索树就是中序遍历。

像这种树的前序、中序、后序遍历，用递归法遍历，唯一区别就是处理代码放在哪里的问题。

它们都会有往左和往右两个递归函数在函数体内部，先左右后，两个内部的递归函数把函数体分为三个部分。

前序遍历就把处理代码放第一个部分，中序遍历就放第二个部分，后序遍历就放第三个部分。

注意所有的递归函数都有退出条件，有时会和错误检查放在一起（比如检查是否为空），一般放置在最前面。

对这道题来说中间的处理就是添加指针，需要找到当前节点的前一个节点，因为我们的代码本身就是按照顺序来的，所以直接记录上一个节点就好了。

又因为需要找到双向链表唯一头节点返回，所以添加了一个if(head==nullptr)的检查，也起到初始化pre的作用。

注意不用的指针都先给置为空指针比较好，避免产生悬空指针问题。