LeetCode Algorithm 897. 递增顺序搜索树

897. 递增顺序搜索树

Ideas

看到搜索二叉树就想到了它的中序遍历序列是有序的，所以干脆直接用中序遍历序列，把每一项的left结点都置为nullptr，right结点置为下一项就OK了。

需要注意中序遍历序列的最后一个节点需要做一些调整：left和right指针都置为空。不然可能会导致出现环。

Code C++

class Solution { public: vector<TreeNode*> middle_order_traversal(TreeNode* node) { TreeNode* item = node; stack<TreeNode*> stk; vector<TreeNode*> ans; while (!stk.empty() || item != nullptr) { if (item != nullptr) { stk.push(item); item = item->left; } else { item = stk.top(); stk.pop(); ans.push_back(item); item = item->right; } } return ans; } TreeNode* increasingBST(TreeNode* root) { vector<TreeNode*> values = middle_order_traversal(root); for (int i = 0; i < values.size(); i++) { if (i == values.size() - 1) { values[i]->left = nullptr; values[i]->right = nullptr; } else { cout << values[i]->val << ", "; values[i]->left = nullptr; values[i]->right = values[i + 1]; } } return values[0]; } };