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 };

LeetCode OJ 题目： 解题思路： 代码：

解题思路：

代码：

相关推荐

LeetCode OJ 题目：解题思路：代码：