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 = valself.left = leftself.right = rightdef recoverTree(root: TreeNode) -> None:x = y = prev = Nonedef inorder(node):nonlocal x, y, previf not node:returninorder(node.left)if prev and prev.val >= node.val:if x is None:x = prevy = nodeprev = nodeinorder(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:returnprint_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 mainimport "fmt"type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func recoverTree(root *TreeNode) {var x, y, prev *TreeNodevar 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 = nodeinorder(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? = nullvar right: TreeNode? = null
}fun recoverTree(root: TreeNode?) {var x: TreeNode? = nullvar y: TreeNode? = nullvar prev: TreeNode? = nullfun inorder(node: TreeNode?) {if (node == null) returninorder(node.left)if (prev != null && prev!!.`val` >= node.`val`) {if (x == null) {x = prev}y = node}prev = nodeinorder(node.right)}inorder(root)// Swap the values of x and yval 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) returnprintInOrder(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()
}
