Recover Binary Search Tree--leetcode难题讲解

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?

https://leetcode.com/problems/recover-binary-search-tree/

二叉排序树中有两个节点被交换了，要求把树恢复成二叉排序树。

最简单的办法，中序遍历二叉树生成序列，然后对序列中排序错误的进行调整。最后再进行一次赋值操作，但这个不符合空间复杂度要求。

需要用两个指针记录错误的那两个元素，然后进行交换。

怎样找出错误的元素？遍历二叉排序树，正确时应该是从小到大，如果出现之前遍历的节点比当前大，则说明出现错误。所以我们需要一个pre指针来指向之前经过的节点。

如果只有一处不符合从小到大，则只用交换这一个地方。第二个指针记录第二个异常点。

Github repository: https://github.com/huashiyiqike/myleetcode

//JAVA CODE：
public class Solution {

    TreeNode first = null, second = null, pre = null;

     //first larger than follow, second smaller than pre

    public void helper(TreeNode root){

        if(root.left != null) helper(root.left);

        if(pre != null && root.val < pre.val){

            if(first == null)

                first = pre;

            second = root;

        }

        pre = root;

        if(root.right != null) helper(root.right);

    }

    public void recoverTree(TreeNode root) {

        helper(root);

        int tmp = first.val;

        first.val = second.val;

        second.val = tmp;

    }

}

//C++ CODE：
#include <iostream>

#include <cstdlib>

struct TreeNode {

    int val;

    TreeNode *left;

    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

    TreeNode *first = NULL, *second = NULL, *last = NULL;

public:

    void inorder(TreeNode* root){

        if(root->left != NULL){

            inorder(root->left);

        }

        if(last != NULL && root->val < last->val){

            if(first == NULL) first = last;

            second = root;

        }

        last = root;

        if(root->right != NULL) inorder(root->right);

    }

    void recoverTree(TreeNode* root) {

        if(root == NULL) return;

        inorder(root);

        if(first && second)

            std::swap(first->val, second->val);

    }

};

#PYTHON CODE：
class Solution:

    def inorderTravel(self, root, last):

        if root.left:

            last = self.inorderTravel(root.left, last)

        if last and last.val > root.val:

            if self.first is None:

                self.first = last

            self.second = root

        last = root

        if root.right:

            last = self.inorderTravel(root.right, last)

        return last

    def recoverTree(self, root):

        if root is None:

            return

        self.first, self.second = None, None

        self.inorderTravel(root, None)

        self.first.val, self.second.val = self.second.val, self.first.val

巴特西

Recover Binary Search Tree--leetcode难题讲解

最新文章

热门文章