题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
递归方法
W:
中序遍历,因为是二叉搜索树,需要定义全局变量防止递归值的改变,递归到最小值为头节点;
如果不是最小值,此时需要建立当前节点与上一个节点的连接;
N:
处理时需要判断上一个节点是否为空
class Solution { public: //返回的第一个指针,即为最小值,先定为NULL TreeNode* head = nullptr; //中序遍历当前值的上一位,初值为最小值,先定为NULL TreeNode* pre = nullptr; TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree== nullptr){ return nullptr; } //中序遍历 Convert(pRootOfTree->left); if(pre== nullptr){//递归到最小值,判断上一位是否为空 head=pRootOfTree; pre=head; } else{ //note use else pRootOfTree->left=pre; pre->right=pRootOfTree; pre=pRootOfTree; } Convert(pRootOfTree->right); return head; } };
迭代方法
W:中序迭代遍历,需要一个标志位来判断是否指向最左侧,赋值为头节点,其他类似于递归调用
修改指向。
N:进入循环判断 cur!=nullptr;
指针定义赋值为空;
每次处理一个节点if ...else...
/* 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) { stack<TreeNode*> st; if(!pRootOfTree) return nullptr; TreeNode* cur=pRootOfTree; TreeNode* pre=nullptr;//note 指针初始赋值为空 TreeNode* head=nullptr; bool isFirst=false; while(cur!=nullptr || !st.empty()){ if(cur!=nullptr){ st.push(cur); cur=cur->left; } else{ cur=st.top(); st.pop(); if(!isFirst){//find the top left node isFirst=true; head=cur; pre=head; } else{ pre->right=cur; cur->left=pre;//note 互相指向 pre=cur;//更新pre; } cur=cur->right;//放在外面 } } return head; } };