LeetCode99. 恢复二叉搜索树

Yuyy

发布于 2022-06-28 20:14:10

1470

发布于 2022-06-28 20:14:10

文章被收录于专栏：yuyy.info技术专栏

本文最后更新于 590 天前，其中的信息可能已经有所发展或是发生改变。

1. 要点

二叉搜索树的特点：中序遍历结果递增，可用来做验证复习下中序遍历（太久没写，写成前后序遍历的先push去了）

2. 题目

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

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

3. 示例 1：

输入：root = [1,3,null,null,2] 输出：[3,1,null,null,2] 解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

4. 示例 2：

输入：root = [3,1,4,null,null,2] 输出：[2,1,4,null,null,3] 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

5. 提示：

树上节点的数目在范围 [2, 1000] 内 -231 <= Node.val <= 231 - 1

6. 代码

public void recoverTree(TreeNode root) {
        TreeNode firstWrongNode = null;
        TreeNode seccondWrongNode = null;
        TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
        Stack<TreeNode> treeNodes = new Stack<>();
        TreeNode tmpRootNode =root;
        while (tmpRootNode!=null||!treeNodes.isEmpty()){
            if(tmpRootNode != null){
                treeNodes.push(tmpRootNode);
                tmpRootNode=tmpRootNode.left;
            }else{
                TreeNode currNode=treeNodes.pop();
                if (firstWrongNode == null && preNode.val> currNode.val){
                    firstWrongNode = preNode;
                }
                if (firstWrongNode != null && preNode.val > currNode.val){
                    seccondWrongNode = currNode;
                }
                preNode = currNode;
                tmpRootNode=currNode.right;
            }
        }
        int tmp =firstWrongNode.val;
        firstWrongNode.val=seccondWrongNode.val;
        seccondWrongNode.val=tmp;
    }

Post Views: 260

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-11-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度