【Leetcode刷题篇】leetcode99 恢复二叉搜索树
发布日期:2021-06-29 15:33:28
浏览次数:3
分类:技术文章
本文共 1022 字,大约阅读时间需要 3 分钟。
题目:给你二叉搜索树的根节点 root ,该树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。
进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗?
解题思路一、对其中序遍历存储其所有结点的值,对其中的值进行遍历,存储器异常值,对树进行遍历,找到异常值,并进行替换。
public void recoverTree(TreeNode root) { Listnums = new ArrayList<>(); inorder(root,nums); // 获取不正确的两个位置 int[] swapped = findTwoSwapped(nums); recover(root,2,swapped[0],swapped[1]); } // 中序遍历获取结果 public void inorder(TreeNode root,List nums) { if(root==null) { return; } inorder(root.left,nums); nums.add(root.val); inorder(root.right,nums); } // 获得中序遍历不确定的两个位置 public int[] findTwoSwapped(List nums) { int n = nums.size(); int x = -1,y=-1;; for(int i=0;i
题解二、中序遍历的隐式遍历过程中寻找其异常值。
// 二叉搜索树的隐式恢复 public void recoverTree_2(TreeNode root) { Stackstack = new Stack<>(); TreeNode x = null, y = null, pred= null; while(!stack.isEmpty()||root!=null) { while(root!=null) { stack.push(root); root = root.left; } root = stack.pop(); if(pred!=null&&root.val
转载地址:https://codingchaozhang.blog.csdn.net/article/details/109499745 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月23日 18时38分19秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
EasyDSS平台接入设备量过多的情况下如何进行批量推流测试?
2019-04-29
mysql数据库操作基础
2019-04-29
Mariadb基础管理
2019-04-29
awk 的内置变量 NF、NR、FNR、FS、OFS、RS、ORS
2019-04-29
CentOS系统内核升级攻略
2019-04-29
linux系统时区修改(Debian的主机和docker)
2019-04-29
docker-compose 安装
2019-04-29
crontab 定时任务
2019-04-29
查看docker veth pair与宿主机上网卡的对应关系
2019-04-29
使用 GitLab CI 进行持续集成的一些踩坑
2019-04-29
企业云盘给贸易业带来新的效益
2019-04-29
Linux入门常用命令
2019-04-29
Spring整理
2019-04-29
SpringMvc加强
2019-04-29
初识Vue全家桶 Nuxt.js(一)
2019-04-29
基本路由及动态路由(二)
2019-04-29