By

文章目录
  1. 1. Recover Binary Search Tree
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题

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?

思路

中序遍历，找出两个逆序的位置。

解题

c++版

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
/**
 * 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 {
public:
    TreeNode *s1,*s2,*pre;
    void recoverTree(TreeNode* root) {
        if(!root)
            return;
        s1=s2=pre=NULL;
        Inorder(root);
        swap(s1->val,s2->val);
    }
    
    void Inorder(TreeNode* root){
        if(!root) return;
        Inorder(root->left);
        if(pre && pre->val>=root->val){
            if(!s1){s1=pre;s2=root;}
            else s2=root;
        }
        pre=root;
        Inorder(root->right);
    }
};

python 版

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param {TreeNode} root
    # @return {void} Do not return anything, modify root in-place instead.
    def __init__(self):
        self.s1=None
        self.s2=None
        self.pre=None

    def recoverTree(self, root):
        if(not root):
            return
        self.Inorder(root)
        tmp=self.s1.val
        self.s1.val=self.s2.val
        self.s2.val=tmp
    
    def Inorder(self,root):
        if(not root):
            return
        self.Inorder(root.left)
        if(self.pre!=None and self.pre.val>=root.val):
            if self.s1==None:
                self.s1=self.pre
                self.s2=root
            else:
                self.s2=root
        self.pre=root
        self.Inorder(root.right)
leetcode
leetcode,tree
文章目录
  1. 1. Recover Binary Search Tree
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题