【LeetCode OJ】Recover Binary Search Tree
2024-10-18 03:27:45
Problem Link:
https://oj.leetcode.com/problems/recover-binary-search-tree/
We know that the inorder traversal of a binary search tree should be a sorted array. Therefore, we can compare each node with its previous node in the inorder to find the two swapped elements.
There are at most two cases that current_node < prev_node:
- If the two swapped elements are adjacent, then there is only one occurrence that current_node < prev_node. The two elements are just the current_node and prev_node.
- If the two swapped elements are not neighbors, then there are two occurrences that current_node < prev_node. The two elements are the prev_node in the first occurrence and the current_node in the second occurrence.
The code is as follows.
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
# @param root, a tree node
# @return a tree node
def recoverTree(self, root):
"""
Traverse the tree in the order of inorder and compare the node to its previous node.
There are at most two occurrences that prev_node < current_node, if there are two elements swapped.
If there is only one occurrence, then the two swapped nodes are prev_node and current_node.
If there are two occurrences, then the two swapped nodes are prev_node in the first occurrence and current_node in the second occurrence.
"""
prev_node = None
current_node = None
stack = []
p = root
res1 = None
res2 = None
while stack or p:
if p:
stack.append(p)
p = p.left
else:
current_node = stack.pop()
# Compare current node and previous node
if prev_node:
if prev_node.val > current_node.val:
if res1:
res2 = current_node
break
else:
res1 = prev_node
res2 = current_node
prev_node = current_node
p = current_node.right
res1.val, res2.val = res2.val, res1.val
return root
最新文章
- 【CodeVS2800】 送外卖 最短路+状压DP
- Node.js 手册查询-3-Mongoose 方法
- sql(SqlServer)编程基本语法
- 重写OnPaint事件对窗体重绘(显示gif动画) 实例2
- Tomcat 设置自动编译,自动发布,自动部署
- 微信小程序支付步骤
- 【基础】新手任务,五分钟全面掌握JQuery选择器
- Memcached的配置,SSH项目中的整合(com.whalin),Memcached工具类,Memcached的代码调用
- 点云格式-pcd
- linux resin 基本站点配置
- Power BI 与 Azure Analysis Services 的数据关联:4、Power BI 连接到Azure Analysis Services 并展示
- 12C -- 配置Application Continuity
- MyISAM和InnoDB区别 及选择
- MySQL 的 CURD 操作
- 开机自启动nginx,php-fpm
- 快递 API接口
- docker 配置远程访问
- EF 使用 oracle
- COM组件技术名称解释
- JxBrowser概述与简单应用
热门文章
- NGUI制作属于自己Button
- 使用robot frame selenium中遇到的问题汇总
- Python:循环语句
- 利用ajax向jsp传输数据
- 艺萌TCP文件传输及自动更新系统介绍(TCP文件传输)(四)
- Shell父进程获取子进程的变量值
- EntityFrame Work:No Entity Framework provider found for the ADO.NET provider with invariant name &#39;System.Data.SqlClient&#39;
- ";$cond";
- 在 Xcode 7 中安装 Alcatraz
- Bootstrap <;基础十八>;面包屑导航(Breadcrumbs)