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

提示：

树上节点的数目在范围 [2, 1000] 内

-231 = 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)

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)
}

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()
}