給你二叉搜索樹的根節點 root ，該樹中的 恰好 兩個節點的值被錯誤地交換。請在不改變其結構的情況下，恢復這棵樹 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/recover-binary-search-tree

例：

輸入：root = [1,3,null,null,2]
輸出：[3,1,null,null,2]
解釋：3 不能是 1 的左孩子，因為 3 > 1 。交換 1 和 3 使二叉搜索樹有效。

解析：

因為只有兩個節點出了問題，先對搜索樹進行中序遍歷，如果只有一組逆序對，那么只需要調換兩個位置就行了，如果有兩組逆序對，因為右邊的數大于左邊的數，所以位置不對的一定是第一組的第一個較大的數和第二組第二個較小的數，進行調換即可。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = rightclass Solution(object):def __init__(self):self.res = []def recoverTree(self, root):""":type root: TreeNode:rtype: None Do not return anything, modify root in-place instead."""self.mid(root)node1 = None # 第一個錯誤節點node2 = None # 第二個錯誤節點for i in range(len(self.res)-1):if self.res[i].val > self.res[i+1].val and node1 == None: # 只有一組逆序對node1 = self.res[i]node2 = self.res[i+1]elif self.res[i].val > self.res[i+1].val and node1 !=None: # 有兩組逆序對node2 = self.res[i+1] node1.val, node2.val = node2.val, node1.val # 將兩個數進行對調def mid(self, root): # 中序遍歷if root is not None:self.mid(root.left)self.res.append(root)self.mid(root.right)

?

總結

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

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