刷题——二叉搜索树与双向链表

二叉搜索树与双向链表_牛客题霸_牛客网

方法一：

void dfs(TreeNode* pRootOfTree, TreeNode* &pre){if(pRootOfTree == NULL)return;dfs(pRootOfTree->left, pre);//所有左子树if(pre)pre->right = pRootOfTree;pRootOfTree->left = pre;pre = pRootOfTree;//更新pre到下一个结点dfs(pRootOfTree->right, pre);//所有结点的右子树}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == NULL) return pRootOfTree;TreeNode* pre = NULL;dfs(pRootOfTree, pre);TreeNode* head = pRootOfTree;//找链表头结点while(head->left){head = head->left;}return head;}

方法二：

TreeNode* pre = NULL,*head = NULL;void dfs(TreeNode* pRootOfTree){if(pRootOfTree == NULL) return;dfs(pRootOfTree->left);//所有左子树if(pre) pre->right = pRootOfTree;else head = pRootOfTree;pRootOfTree->left = pre;pre = pRootOfTree;//更新pre到下一个结点dfs(pRootOfTree->right);//所有结点的右子树}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == NULL) return pRootOfTree;dfs(pRootOfTree);head->left = pre;//最后一个结点pre->right = head;//最前一个结点return head;}