LeetCode OJ - Recover Binary Search Tree

題目：

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，在遍歷過程中記錄出現錯誤的節點。err_1是第一次發生pre_val > root_val的節點，err_2是最后一次發生pre_val > root_val的節點。最后交換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 };

轉載于:https://www.cnblogs.com/dongguangqing/p/3737265.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/260427.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/260427.shtml
英文地址，請注明出處：http://en.pswp.cn/news/260427.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！