LeetCode 重构二叉搜索数,即找出两个被交换的节点

2024-09-03 00:58

本文主要是介绍LeetCode 重构二叉搜索数,即找出两个被交换的节点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题:Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.


OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1/ \2   3/4\5
The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

题意:二叉搜索树中,有两个结点的位置被交换了,请找出这两个结点并交换回来。

“直观的想法可能是中序遍历一遍二叉树,得到一个有序的二叉树,然后找出其中逆序的地方,交换回来就好了。但这样空间复杂度就是O(n),题目要求O(1)。

我们来分析下有哪些情况:1) 被交换的两个结点相邻,如124356,这样只需要把相邻的3和4交换回来即可;2) 被交换的两个结点不相邻,如163452,这样我们需要找出两个逆序的地方,63和52,并交换第一个逆序的前者和第二个逆序的后者。”(http://blog.csdn.net/ljiabin/article/details/44514651该博主很认真解释了一下,不然光看程序还真看不懂)。因为这两种情况存在,而且这可二叉树只有两个节点被交换了,所以我们需要定位这两个节点,而不是将相邻节点一对一对的交换达到这种效果。这一点也是最精妙的地方,程序中mistake1记录的最底下出错的节点,mistake2记录的是中序遍历中较mistake1后面的节点。


import java.util.*;
/**
 * Definition for binary tree*/
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; 
      }
 }
class Solution {
private TreeNode pre=null;
private TreeNode mistake1,mistake2=null;
public void recoverTree(TreeNode root) {
inOrderTraversal(root);
int temp=mistake2.val;
mistake2.val=mistake1.val;
mistake1.val=temp;
}
/*中序遍历查找出错的两个节点,只有两个节点出错哦
* 左节点值<根节点值<右节点值
* 首先从左子树遍历到底
* */
public void inOrderTraversal(TreeNode root){
if(root==null)
return;
//中序遍历
inOrderTraversal(root.left);//左子树遍历到底
if(pre!=null&&pre.val>root.val){
if(mistake1==null)
mistake1=pre;
mistake2=root;
}
pre=root;//最底下的左节点
inOrderTraversal(root.right);
}

这篇关于LeetCode 重构二叉搜索数,即找出两个被交换的节点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131575

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists