【递归,链表,BST】将BST转换成双向链表
二叉搜索树与双向链表
http://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5
既然是一棵树,可以考虑递归做法。
- 如果左子树和右子树都已经处理好了,该怎么组合成一个新的链表?
- 有点类似数学归纳法的思路
以图片为例,左子树和右子树处理好之后,返回红色节点为head的双向链表,所以只需要将这两段链表和root合并即可
- 合并之后返回的仍然是左子树的head(若有)
边界情况
- 若整个树为空,显然应该返回nullptr
- 若左子树为空,则答案的head应该为root
- 若右子树为空,则root->right 自然是nullptr,不需要特别处理
code:
TreeNode* Convert(TreeNode* pRootOfTree){ //处理空树 if(pRootOfTree == nullptr) return nullptr; TreeNode * ans = nullptr; //处理左子树(若有) if(pRootOfTree->left){ ans = Convert(pRootOfTree->left); auto tail = ans; while(tail->right) tail = tail->right; tail->right = pRootOfTree; //处理左子树链表和root的衔接 pRootOfTree->left = tail; }else ans = pRootOfTree; //若无左子树,head设置为root if(pRootOfTree->right){ //处理右子树 auto nxtHalf = Convert(pRootOfTree->right); nxtHalf->left = pRootOfTree; pRootOfTree->right = nxtHalf; } return ans; }