聖地亞歌

Leetcode P0099"Recover Binary Search Tree" 题解

2020/09/02 Leetcode

博文中会简要介绍Leetcode P0099题目分析及解题思路。

“Recover Binary Search Tree”是一道比较经典的考察二叉搜索树（Binary Search Tree，BST）性质的问题。关于BST的性质，我们知道对于在BST上的任意一个树结点，其值要大于它左子树的最大值，小于其右子树的最小值，而且它的中序遍历后的序列是一个递增序列。根据这些性质我们就可以还原一个二叉搜索树。

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]

   1
  /
 3
  \
   2

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

   3
  /
 1
  \
   2
Plaintext

最基本的思路是，先通过中序遍历得到一个数组，根据BST的性质，这个数组本应该是递增有序的数组，但是由于我们调换了其中两个树结点的值，在现在这个数组中将会存在最多两个极大值点或者说极小值点（不含两端），假设为k个。我们很容易地可以发现，第1个极大值点的值和第k-1个极小值点的值是被调换的两个值，那么我们得到这两个树结点以后，再调换值即可还原二叉搜索树。

以下是Java的题解代码实现。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void recoverTree(TreeNode root) {
        
        Deque<TreeNode> stack = new LinkedList<>();
        List<TreeNode> orderedSequence = new ArrayList<>();
        TreeNode curr = root;
        // Iterative
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.offerFirst(curr);
                curr = curr.left;
            }
            
            curr = stack.pollFirst();
            orderedSequence.add(curr);
            curr = curr.right;
        }
        
        TreeNode big = null, small = null;
        int size = orderedSequence.size();
        for (int itr=0; itr<size-1; ++itr) {
            if (orderedSequence.get(itr).val < orderedSequence.get(itr+1).val) 
                continue;
            
            if (big == null) {
                big = orderedSequence.get(itr);
                small = orderedSequence.get(itr+1);
            }
            else 
                small = orderedSequence.get(itr+1);
        }
        
        int temp = big.val;
        big.val = small.val;
        small.val = temp;
    }
}
Java

以下是C++的题解代码实现。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        
        stack<TreeNode*> nodes;
        vector<TreeNode*> ordered_nodes;
        TreeNode *curr = root;
        while (curr != NULL || !nodes.empty()) {
            while (curr != NULL) {
                nodes.push(curr);
                curr = curr->left;
            }
            
            curr = nodes.top();
            nodes.pop();
            ordered_nodes.push_back(curr);
            curr = curr->right;
        }
        
        TreeNode *big = NULL, *small = NULL;
        for (int itr=0; itr<ordered_nodes.size()-1; ++itr) {
            if (ordered_nodes[itr]->val < ordered_nodes[itr+1]->val) 
                continue;
            
            if (big == NULL) {
                big = ordered_nodes[itr];
                small = ordered_nodes[itr+1];
            }
            else
                small = ordered_nodes[itr+1];
        }
        
        swap(big->val, small->val);
    }
};
C++

Search