1. 題目

二叉搜索樹中的兩個節(jié)點被錯誤地交換。

請在不改變其結(jié)構(gòu)的情況下，恢復(fù)這棵樹。
你能想出一個只使用常數(shù)空間的解決方案嗎？

2. 解題

• 循環(huán)中序遍歷（棧），記錄不滿足的節(jié)點，交換其val
• $O(n)$ 空間復(fù)雜度
  

class Solution { public:void recoverTree(TreeNode* root) {if(root == NULL)return;TreeNode *node1 = NULL, *node2 = NULL, *prev = NULL;stack<TreeNode*> stk;while(root || !stk.empty()){while(root){stk.push(root);root = root-> left;}root = stk.top(); if(prev && prev->val > root->val){node1 = node1 ? node1 : prev;//node1只被賦值一次node2 = root;//被交換的數(shù)相鄰，node2只賦值一次，否則2次}prev = root;root = stk.top()->right;stk.pop();}swap(node1->val, node2->val);} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 99. 恢复二叉搜索树（中序遍历）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。