leetcode--恢复二叉搜索树

leetcode地址：恢复二叉搜索树
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：
树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1

实现思路

这个问题要求恢复一个二叉搜索树，其中恰好有两个节点的值被错误地交换了，但是不改变其结构。二叉搜索树的特性是左子树的所有节点小于根节点，右子树的所有节点大于根节点。

中序遍历
二叉搜索树进行中序遍历得到的序列应该是递增的。如果有两个节点交换了位置，会导致中序遍历序列中出现一对不满足递增关系的节点。
寻找错误节点
在中序遍历过程中，记录前驱节点和当前节点。
如果出现前驱节点的值大于当前节点的值，则这两个节点是需要交换的节点。
恢复节点
如果发现了需要交换的节点，记录下来。
最后交换这两个节点的值，使得树恢复为二叉搜索树的结构。

代码详解

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def recoverTree(root: TreeNode) -> None:
    x = y = prev = None
    
    def inorder(node):
        nonlocal x, y, prev
        if not node:
            return
        
        inorder(node.left)
        
        if prev and prev.val >= node.val:
            if x is None:
                x = prev
            y = node
        
        prev = node
        
        inorder(node.right)
    
    inorder(root)
    
    x.val, y.val = y.val, x.val

# Helper function to print inorder traversal
def print_inorder(root):
    if not root:
        return
    print_inorder(root.left)
    print(root.val, end=" ")
    print_inorder(root.right)

# Example usage:
# Example 1: [1,3,null,null,2]
root1 = TreeNode(1)
root1.right = TreeNode(3)
root1.right.left = TreeNode(2)

print("Before recovery:")
print_inorder(root1)
print()

recoverTree(root1)

print("After recovery:")
print_inorder(root1)

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
41
42
43
44
45
46
47
48
49
50
51
52
53

go实现

package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func recoverTree(root *TreeNode) {
	var x, y, prev *TreeNode
	var inorder func(*TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)
		if prev != nil && prev.Val >= node.Val {
			if x == nil {
				x = prev
			}
			y = node
		}
		prev = node
		inorder(node.Right)
	}

	inorder(root)
	x.Val, y.Val = y.Val, x.Val
}

// Helper function to print inorder traversal
func printInorder(root *TreeNode) {
	if root == nil {
		return
	}
	printInorder(root.Left)
	fmt.Printf("%d ", root.Val)
	printInorder(root.Right)
}

func main() {
	// Example 1: [1,3,null,null,2]
	root := &TreeNode{Val: 1}
	root.Right = &TreeNode{Val: 3}
	root.Right.Left = &TreeNode{Val: 2}

	fmt.Println("Before recovery:")
	printInorder(root)
	fmt.Println()

	recoverTree(root)

	fmt.Println("After recovery:")
	printInorder(root)
}

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

kotlin实现

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun recoverTree(root: TreeNode?) {
    var x: TreeNode? = null
    var y: TreeNode? = null
    var prev: TreeNode? = null
    
    fun inorder(node: TreeNode?) {
        if (node == null) return
        
        inorder(node.left)
        
        if (prev != null && prev!!.`val` >= node.`val`) {
            if (x == null) {
                x = prev
            }
            y = node
        }
        prev = node
        
        inorder(node.right)
    }
    
    inorder(root)
    
    // Swap the values of x and y
    val temp = x!!.`val`
    x!!.`val` = y!!.`val`
    y!!.`val` = temp
}

// Helper function to print the tree in-order
fun printInOrder(node: TreeNode?) {
    if (node == null) return
    printInOrder(node.left)
    print("${node.`val`} ")
    printInOrder(node.right)
}

fun main() {
    // Example 1: [1,3,null,null,2]
    val root1 = TreeNode(1)
    root1.right = TreeNode(3)
    root1.right!!.left = TreeNode(2)
    
    println("Before recovery:")
    printInOrder(root1)
    println()
    
    recoverTree(root1)
    
    println("After recovery:")
    printInOrder(root1)
    println()
}

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59