?1、題目描述
二叉搜索樹中的兩個節點被錯誤地交換。

請在不改變其結構的情況下，恢復這棵樹。

示例 1:

示例 2:

?

//顯示中序遍歷 func recoverTree(root *TreeNode) {nums := []int{}var inorder func(node *TreeNode)inorder = func(node *TreeNode) {if node == nil {return}inorder(node.Left)nums = append(nums, node.Val)inorder(node.Right)}inorder(root)x, y := findTwoSwapped(nums)fmt.Println(x, y)recover(root, 2, x, y) }//x取大數，y取小數 func findTwoSwapped(nums []int) (int, int) {x, y := -1, -1for i := 0; i < len(nums) - 1; i++ {if nums[i + 1] < nums[i] {y = nums[i+1]if x == -1 {x = nums[i]} else {break}}}return x, y }func recover(root *TreeNode, count, x, y int) {if root == nil {return}if root.Val == x || root.Val == y {if root.Val == x {root.Val = y} else {root.Val = x}//記錄交換次數，要雙方都賦值才算交換完成count--if count == 0 {return}}//遞歸recover(root.Right, count, x, y)recover(root.Left, count, x, y) }//隱式中序遍歷 func recoverTree(root *TreeNode) {stack := []*TreeNode{}var x, y, pred *TreeNodefor len(stack) > 0 || root != nil {for root != nil {stack = append(stack, root)//一路向左root = root.Left}//通過出棧實現中序遍歷root = stack[len(stack)-1]stack = stack[:len(stack)-1]if pred != nil && root.Val < pred.Val {y = rootif x == nil {x = pred} else {break}}pred = rootroot = root.Right}x.Val, y.Val = y.Val, x.Val }

?

總結

以上是生活随笔為你收集整理的算法：恢复二叉搜索树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。