golang刷leetcode 恢复二叉搜索树

golangLeetcode

发布于 2022-08-02 15:47:30

1760

发布于 2022-08-02 15:47:30

文章被收录于专栏：golang算法架构leetcode技术php

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

进阶:

使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？

解题思路：

1，二叉树的性质：左子树<根<小于右子树

2，如果中序遍历二叉树就能得到一个递增的序列

3，由于只交换了两个位置，假设这两个位置为first，second，则first左边小于first，右边大于first，second的左边都小于second，只需交换first，second位置即可

4，如何得到递增序列？

中序遍历

5，用pre记录中序遍历的上一个位置，如果pre.val>cur.val说明pre的位置放错了，用first，second 记录两个位置，最好交换即可

6，注意，由于使用了全局指针，所以，使用前一定要初始化，否则结果很奇怪

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var pre,first,second *TreeNode

func recoverTree(root *TreeNode)  {
    pre=nil
    first=nil
    second =nil
    midOrder(root) 

    temp:=first.Val
    first.Val=second.Val
    second.Val=temp
   
    return
}

func midOrder(cur *TreeNode){
    if cur==nil{
        return
    }
    midOrder(cur.Left)
    if pre!=nil && pre.Val>cur.Val{
        if first==nil{
            first=pre
            second=cur
        }else{
            second=cur
        }
    }
    pre=cur
     midOrder(cur.Right)
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-03-08，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法