算法设计与分析-Week4

发表于 | 更新于

Recover Binary Search Tree

题目描述

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]
Output: [3,1,null,null,2]

Example 2:

Input: [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]

解题思路

题目描述的二叉搜索树有两个元素交换了位置，需要将其找出。由于二叉搜索树用中序遍历所得到的序列是递增的，因此对此二叉搜索树进行中序遍历得到的序列必定有两个元素不符合递增的规律，我在遍历过程中找出这两个元素，记为first和second，并在遍历完成后将其交换，以得到正确的二叉搜索树。
第一个错误的元素first必定大于其后的一个元素，第二个错误的元素second必定小于其前面的一个元素，因此我用一个preNode记录前一个元素，先找出第一个错误的元素first后，找出第二个错误的元素second，最后进行交换。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode* first;
    TreeNode* second;
    TreeNode* preNode;
public:
    Solution() {
        first = NULL;
        second = NULL;
        preNode = new TreeNode(INT_MIN);
    }
    void recoverTree(TreeNode* root) {
        traverse(root);
        /*交换两个错误的元素*/
        int temp = first->val;
        first->val = second->val;
        second->val = temp;
    }
    void traverse(TreeNode* root) {
        if(root == NULL) return;
        traverse(root->left);
        if(first == NULL && preNode->val > root->val) {
            first = preNode;
        }
        if(first != NULL && preNode->val > root->val) {
            second = root;
        }
        preNode = root;
        traverse(root->right);
    }
};
0%