📑 题目：99. 恢复二叉搜索树

🚀 本题 LeetCode 传送门

题目大意

二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

解题思路

  • 在二叉搜索树中，有 2 个结点的值出错了，要求修复这两个结点。
  • 这一题按照先根遍历 1 次就可以找到这两个出问题的结点，因为先访问根节点，然后左孩子，右孩子。用先根遍历二叉搜索树的时候，根结点比左子树都要大，根结点比右子树都要小。所以左子树比根结点大的话，就是出现了乱序；根节点比右子树大的话，就是出现了乱序。遍历过程中在左子树中如果出现了前一次遍历的结点的值大于此次根节点的值，这就出现了出错结点了，记录下来。继续遍历直到找到第二个这样的结点。最后交换这两个结点的时候，只是交换他们的值就可以了，而不是交换这两个结点相应的指针指向。

代码

  1. package leetcode
  3. /**
  4.  * Definition for a binary tree node.
  5.  * type TreeNode struct {
  6.  *     Val int
  7.  *     Left *TreeNode
  8.  *     Right *TreeNode
  9.  * }
  10.  */
  11. func recoverTree(root *TreeNode) {
  12.  var prev, target1, target2 *TreeNode
  13.  _, target1, target2 = inOrderTraverse(root, prev, target1, target2)
  14.  if target1 != nil && target2 != nil {
  15.   target1.Val, target2.Val = target2.Val, target1.Val
  16.  }
  18. }
  20. func inOrderTraverse(root, prev, target1, target2 *TreeNode) (*TreeNode, *TreeNode, *TreeNode) {
  21.  if root == nil {
  22.   return prev, target1, target2
  23.  }
  24.  prev, target1, target2 = inOrderTraverse(root.Left, prev, target1, target2)
  25.  if prev != nil && prev.Val > root.Val {
  26.   if target1 == nil {
  27.    target1 = prev
  28.   }
  29.   target2 = root
  30.  }
  31.  prev = root
  32.  prev, target1, target2 = inOrderTraverse(root.Right, prev, target1, target2)
  33.  return prev, target1, target2
  34. }