題目：

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

解題思路：

中序遍歷BST，在遍歷過程中記錄出現(xiàn)錯(cuò)誤的節(jié)點(diǎn)。err_1是第一次發(fā)生pre_val > root_val的節(jié)點(diǎn)，err_2是最后一次發(fā)生pre_val > root_val的節(jié)點(diǎn)。最后交換err_1->val 和 err_2->val

代碼：

1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 TreeNode *err_1, *err_2; 13 TreeNode *pre; 14 15 void find2Nodes(TreeNode *root) { 16 if (root == NULL) return; 17 18 if (root->left != NULL) { 19 find2Nodes(root->left); 20 } 21 if (pre != NULL && pre->val >= root->val) { 22 if (err_1 == NULL) err_1 = pre; 23 err_2 = root; 24 } 25 pre = root; 26 if (root->right != NULL) { 27 find2Nodes(root->right); 28 } 29 } 30 31 void recoverTree(TreeNode *root) { 32 if (root == NULL) return; 33 34 err_1 = err_2 = pre = NULL; 35 36 find2Nodes(root); 37 swap(err_1->val, err_2->val); 38 } 39 };

?

轉(zhuǎn)載于:https://www.cnblogs.com/dongguangqing/p/3737265.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的LeetCode OJ - Recover Binary Search Tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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