99. 恢复二叉搜索树

女爷i 2022-10-08 02:28 76阅读 0赞

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

class Solution {
           TreeNode pre=new TreeNode(Integer.MIN_VALUE);
             TreeNode first=null;
             TreeNode second=null;
        public void recoverTree(TreeNode root) {
            /**
            中序遍历正确
            123456
            中序遍历有节点交换的
            143256-> 4>3  3>2  我们想要交换4和2  也就是第一个>关系里面的第一个数, 第二个>关系的第二个数  节点不变,交换值即可
             */
          
             helper(root);
             //交换两个节点
             int temp=first.val;
             first.val=second.val;
             second.val=temp;
        }
    
        public void helper(TreeNode node){
            if(node==null)return ;
             helper(node.left);
            if(first==null&&pre.val>node.val) first=pre;
            if(first!=null&&pre.val>node.val) second=node;
            pre=node;
            helper(node.right);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/e284329d855f425796cf7dacbf0bb6d0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，76人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉搜索树、平衡二叉树

一、二叉搜索树这里我们不用太多书面化的语言来定义，笔者认为在讨论数据结构、算法相关的内容时用太多书面化、学术化的语言是一种让人很烦的事情。咬文嚼字，不便于读者理解。

阳光穿透心脏的1/2处/ 2023年10月18日 22:26/ 0 赞/ 30 阅读

相关 leetcode 99. 恢复二叉搜索树

中序遍历，弄在数组里面，再弄个数组复制一份排好序比较哪里错了，换回来中序遍历的时候用map存一下数字的地址（默认没有重复元素） class Solutio

港控/mmm°/ 2023年06月08日 03:19/ 0 赞/ 72 阅读

相关恢复二叉搜索树

恢复二叉搜索树 ![format_png][] ![format_png 1][] -------------------- / 二叉树类定义 /

迈不过友情╰/ 2023年02月23日 07:51/ 0 赞/ 43 阅读

相关 LeetCode 98验证二叉搜素树(中序遍历)&99恢复二叉搜索树

> 微信搜一搜：`bigsai` > [大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1] > 关注回复进群即可加入力扣打卡群，欢迎划水。近期打卡：

柔情只为你懂/ 2023年01月01日 14:49/ 0 赞/ 107 阅读

相关 [Leetcode][第99题][JAVA][恢复二叉搜索树][中序遍历]

【问题描述】\[困难\] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

亦凉/ 2022年11月25日 10:27/ 0 赞/ 88 阅读

相关 99. 恢复二叉搜索树

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

女爷i/ 2022年10月08日 02:28/ 0 赞/ 77 阅读

相关二叉搜索树

在计算机术语中，二叉搜索树又叫二叉查找树、二叉排序树。二叉搜索树（Binary Search Tree）的定义：它或者是一棵空树，或者是具有下列性质的二叉树：若它的

Myth丶恋晨/ 2022年09月30日 06:45/ 0 赞/ 190 阅读

相关二叉搜索树

二叉搜索树的特征定义就是：一个节点的左子节点的关键字值小于这个节点，右子节点的关键字大于或等于这个父节点 package Trees; import java.ut

客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 268 阅读

相关二叉搜索树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy

た入场券/ 2022年03月17日 02:18/ 0 赞/ 265 阅读

相关二叉搜索树

二叉搜索树基本概念二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 337 阅读