牛客——二叉树搜索树转换成排序双向链表

有礼貌的灰绅士

发布于 2023-04-17 20:14:38

1020

发布于 2023-04-17 20:14:38

这道题要求空间复杂度为O(1)，如果没有这个条件可以创建一个vector将所有结点放进去之后进行操作。所以这道题的思路可以用三叉链的方法，就是一个结点可以多出一个指向父节点的指针。我们创建出一个指针front，这个指针指向的是中序遍历中的指针的上一个位置，用于前后进行链接。用递归。

遍历的结点遍历完左再向右，向右的过程中，正好到了4的位置，4的左指针指向前驱，前驱是什么都没有，所以指向空就可以了，然后让右指针指向父节点，这个时候我们并不知道父节点，那么这时可以将指针front指向这里，然后本身返回上一层访问的就是父节点（这里是6），这个时候本来是要访问右子树的，在这个过程中让front指针的右指针指向该节点，就完成了一次链接，以此循环就可以了。最后一步退出之后front指向16的结点，该节点没有后继，所以不需要指向空指针。（这里其实随意）

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	void linked(TreeNode* root, TreeNode*& front)
	{
		if(root == nullptr)
			return ;
		linked(root->left, front);
		root->left =  front;
		if(front)//如果front为空就说明不需要让front指向谁
			front->right = root;
		front = root;
		linked(root->right, front);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* front = nullptr;
		TreeNode* root = pRootOfTree;
		linked(root, front);
		while(root && root->left)//找到链表表头
			root = root->left;
		return root;
    }
};