题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
//利用栈辅助遍历,时间复杂度O(n),空间复杂度O(n) /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ #include <cstddef> #include <stack> class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) { if (pRootOfTree==NULL) { return NULL; } stack<TreeNode*> s; TreeNode* pre; TreeNode* head; bool flag=true; while (pRootOfTree || !s.empty()) { while (pRootOfTree) { s.push(pRootOfTree); pRootOfTree=pRootOfTree->left; } pRootOfTree=s.top(); s.pop(); if (flag) { head=pRootOfTree; pre=head; flag=false; }else{ pre->right=pRootOfTree; pRootOfTree->left=pre; pre=pRootOfTree; } pRootOfTree=pRootOfTree->right; } return head; } };