二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
根据题意,我们需要将搜索二叉树转换成有序的形式。
重点一:BST的中序遍历一定是有序的
因此,此题无论如何都需要使用中序。
又因为要求原地算法,所以:
重点二:中序遍历的第一个节点就是最左的节点,在走到最左节点之前,prev都应该指向nullptr
所以只有在遍历到节点之后,才需要让prev=cur,之前的向左递归的步骤都不需要也不能让prev跟上cur的值。
实现代码如下:
class Solution {
public:void Inorder(TreeNode* cur,TreeNode*& prev){/*cur是在递归的中序遍历,所以一定不传引用,而prev必须一直传引用*/if(cur==nullptr){//prev = cur;return ;}//prev = cur;Inorder(cur->left,prev);//prev表示的是当前遍历节点的上一个有效位置cur->left = prev;if(prev) prev->right = cur;prev = cur ;Inorder(cur->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree==nullptr) return nullptr;TreeNode* cur = pRootOfTree;TreeNode* prev = nullptr;Inorder(cur,prev);TreeNode* head = pRootOfTree;while(head->left){head = head->left;}return head;}
};
重点三:关于在递归中设计不递归的变量
cur作为中序遍历的对象,在递归过程中一直使用传值传参
而prev作为非递归对象,需要他一直保持一个值,所以一定使用传引用传参。