package git.snippet.leetcode;
import java.util.Stack;
// 给定一个棵搜索二叉树的头节点head,其中有两个节点错了,交换过来就能让整棵树重新变成搜索二叉树,怎么找到并调整正确?
// Leetcode题目:https://leetcode.com/problems/recover-binary-search-tree/
// TODO 其实应该要调整两个节点,而不是只是把节点的值进行替换
public class LeetCode_0099_RecoverBinarySearchTree {
// Morris遍历,最优解,空间复杂度O(1)
// 中序遍历
// 第一个错误节点:第一次降序的头节点
// 第二个错误节点:第二次降序的尾节点
// 这里只需要交换两个节点的val就可以AC,
// 实际上更好的处理方式应该是节点真实的进行交换
// 如果能过leetcode,只需要提交这个方法即可
// 但其实recoverTree2才是正路,只不过leetcode没有那么考
public static void recoverTree(TreeNode root) {
TreeNode[] errors = twoErrors(root);
if (errors[0] != null && errors[1] != null) {
int tmp = errors[0].val;
errors[0].val = errors[1].val;
errors[1].val = tmp;
}
}
public static TreeNode[] twoErrors(TreeNode head) {
TreeNode[] ans = new TreeNode[2];
if (head == null) {
return ans;
}
TreeNode cur = head;
TreeNode mostRight = null;
TreeNode pre = null;
TreeNode e1 = null;
TreeNode e2 = null;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
}
if (pre != null && pre.val >= cur.val) {
e1 = e1 == null ? pre : e1;
e2 = cur;
}
pre = cur;
cur = cur.right;
}
ans[0] = e1;
ans[1] = e2;
return ans;
}
// 以下的方法,提交leetcode是通过不了的,但那是因为leetcode的验证方式有问题
// 但其实!以下的方法,才是正路!在结构上彻底交换两个节点,而不是值交换
public static TreeNode recoverTree2(TreeNode head) {
TreeNode[] errs = getTwoErrNodes(head);
TreeNode[] parents = getTwoErrParents(head, errs[0], errs[1]);
TreeNode e1 = errs[0];
TreeNode e1P = parents[0];
TreeNode e1L = e1.left;
TreeNode e1R = e1.right;
TreeNode e2 = errs[1];
TreeNode e2P = parents[1];
TreeNode e2L = e2.left;
TreeNode e2R = e2.right;
if (e1 == head) {
if (e1 == e2P) {
e1.left = e2L;
e1.right = e2R;
e2.right = e1;
e2.left = e1L;
} else if (e2P.left == e2) {
e2P.left = e1;
e2.left = e1L;
e2.right = e1R;
e1.left = e2L;
e1.right = e2R;
} else {
e2P.right = e1;
e2.left = e1L;
e2.right = e1R;
e1.left = e2L;
e1.right = e2R;
}
head = e2;
} else if (e2 == head) {
if (e2 == e1P) {
e2.left = e1L;
e2.right = e1R;
e1.left = e2;
e1.right = e2R;
} else if (e1P.left == e1) {
e1P.left = e2;
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
} else {
e1P.right = e2;
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
}
head = e1;
} else {
if (e1 == e2P) {
if (e1P.left == e1) {
e1P.left = e2;
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1;
} else {
e1P.right = e2;
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1;
}
} else if (e2 == e1P) {
if (e2P.left == e2) {
e2P.left = e1;
e2.left = e1L;
e2.right = e1R;
e1.left = e2;
e1.right = e2R;
} else {
e2P.right = e1;
e2.left = e1L;
e2.right = e1R;
e1.left = e2;
e1.right = e2R;
}
} else {
if (e1P.left == e1) {
if (e2P.left == e2) {
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
e1P.left = e2;
e2P.left = e1;
} else {
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
e1P.left = e2;
e2P.right = e1;
}
} else {
if (e2P.left == e2) {
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
e1P.right = e2;
e2P.left = e1;
} else {
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
e1P.right = e2;
e2P.right = e1;
}
}
}
}
return head;
}
public static TreeNode[] getTwoErrNodes(TreeNode head) {
TreeNode[] errs = new TreeNode[2];
if (head == null) {
return errs;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode pre = null;
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
if (pre != null && pre.val > head.val) {
errs[0] = errs[0] == null ? pre : errs[0];
errs[1] = head;
}
pre = head;
head = head.right;
}
}
return errs;
}
public static TreeNode[] getTwoErrParents(TreeNode head, TreeNode e1, TreeNode e2) {
TreeNode[] parents = new TreeNode[2];
if (head == null) {
return parents;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
if (head.left == e1 || head.right == e1) {
parents[0] = head;
}
if (head.left == e2 || head.right == e2) {
parents[1] = head;
}
head = head.right;
}
}
return parents;
}
// for test -- print tree
public static void printTree(TreeNode head) {
System.out.printl
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何具体存储。例如,数组的连续存储,链表的动态分配节点,树和图的邻接矩阵或邻接表表示等。 基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,使得计算机可以执行以求解问题。 算法特性:包括输入、输出、有穷性、确定性和可行性。即一个有效的算法必须能在有限步骤内结束,并且对于给定的输入产生唯一的确定输出。 算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界法等。 算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
资源推荐
资源详情
资源评论
收起资源包目录
算法和数据结构学习笔记.zip (617个子文件)
setproxy.bat 54B
unsetproxy.bat 38B
.gitignore 428B
LeetCode_0099_RecoverBinarySearchTree.java 18KB
Code_CompareTreeMap.java 16KB
Code_0125_PoemProblem.java 14KB
Code_TreeChainPartition.java 14KB
Code_LightProblem.java 13KB
Code_EveryStepShowBoss.java 13KB
Code_SizeBalancedTreeMap.java 12KB
Code_0117_LCATarjanAndTreeChainPartition.java 11KB
LeetCode_0200_NumberOfIslands.java 11KB
Code_0118_MinCostToYeahArray.java 11KB
LintCode_0550_TopKFrequentWordsII.java 10KB
Code_Heap.java 10KB
Code_AOE.java 10KB
LeetCode_0406_QueueReconstructionByHeight.java 10KB
LeetCode_0010_RegularExpressionMatching.java 10KB
Code_0053_MinCoinsOnePaper.java 10KB
LeetCode_0317_ShortestDistanceFromAllBuildings.java 10KB
LeetCode_0743_NetworkDelayTime.java 9KB
Code_0133_JumpGameOnMatrix.java 9KB
LeetCode_0134_GasStation.java 9KB
Code_AddRemoveGetIndexGreat.java 9KB
Code_SkipListMap.java 9KB
Code_Morris.java 9KB
Code_VisibleMountains.java 8KB
Code_DoubleLinkedListQuickSort.java 8KB
Code_0078_MergeRecord.java 8KB
LeetCode_0460_LFUCache.java 8KB
LeetCode_1478_AllocateMailboxes.java 8KB
Code_AVLTreeMap.java 8KB
Code_0129_Mod3Max.java 8KB
LeetCode_0248_StrobogrammaticNumberIII.java 8KB
Code_0101_RestoreWays.java 8KB
LeetCode_0480_SlidingWindowMedian.java 8KB
LintCode_0629_MinimumSpanningTree.java 8KB
Code_SegmentTree.java 8KB
LeetCode_0327_CountOfRangeSum.java 8KB
Code_0104_Cola.java 8KB
LeetCode_0642_DesignSearchAutocompleteSystem.java 7KB
Code_MakeCoffee.java 7KB
LeetCode_0132_PalindromePartitioningII.java 7KB
LeetCode_0297_SerializeAndDeserializeBinaryTree.java 7KB
Code_IsSum.java 7KB
LeetCode_0126_WordLadderII.java 7KB
LeetCode_0741_CherryPickup.java 7KB
Code_HuffmanTree.java 7KB
Code_0114_PickBands.java 7KB
LeetCode_0887_SuperEggDrop.java 7KB
Code_0018_MinDeleteCost.java 7KB
LeetCode_0691_StickersToSpellWord.java 7KB
LeetCode_0234_PalindromeLinkedList.java 7KB
Code_FindFirstIntersectNode.java 7KB
Code_0128_SplitTo01.java 7KB
NowCoder_LineCoverMax.java 6KB
LeetCode_0494_TargetSum.java 6KB
Code_0123_SumNoPositiveMinCost.java 6KB
LeetCode_0502_IPO.java 6KB
LeetCode_0410_SplitArrayLargestSum.java 6KB
LeetCode_0124_BinaryTreeMaximumPathSum.java 6KB
LeeCodeCN_LCP_03_ProgrammableRobot.java 6KB
Code_0019_CardsProblem.java 6KB
LeetCode_0411_MinimumUniqueWordAbbreviation.java 6KB
LeetCode_1312_MinimumInsertionStepsToMakeAStringPalindrome.java 6KB
LeetCode_0465_OptimalAccountBalancing.java 6KB
LintCode_0477_SurroundedRegions.java 6KB
Code_0052_CoinsWaySameValueSamePaper.java 6KB
LeetCode_0087_ScrambleString.java 6KB
LeetCode_0730_CountDifferentPalindromicSubsequences.java 6KB
NowCoder_BeatMonster.java 6KB
Code02_DynamicSegmentTree.java 6KB
Code_0015_KMinPair.java 6KB
Code_0098_DeleteAdjacentSameCharacter.java 6KB
LeetCode_0639_DecodeWaysII.java 6KB
LeetCode_0148_SortList.java 6KB
Code_0135_GreatWall.java 6KB
NowCoder_MaxSubBSTSize.java 6KB
Code_TrieTree.java 6KB
Code_MonoStack.java 5KB
Code_0084_SplitSumClosedSizeHalf.java 5KB
LeetCode_0803_BricksFallingWhenHit.java 5KB
Code_0116_NotContains4.java 5KB
LeetCode_0102_BinaryTreeLevelOrderTraversal.java 5KB
NowCoder_BiggestTopology.java 5KB
Code_0127_AllSame.java 5KB
NowCoder_MostZeroSplitEor.java 5KB
LeetCode_0004_MedianOfTwoSortedArrays.java 5KB
Code_0070_BestSplitForEveryPosition.java 5KB
Code_0055_NCardsABWin.java 5KB
LeetCodeCN_0062_Josephus.java 5KB
Code_0045_SubSequenceMaxModM.java 5KB
NowCoder_MST2.java 5KB
LintCode_0127_TopologicalSorting.java 5KB
Code_DC3.java 5KB
LeetCode_0699_FallingSquares.java 5KB
Code_0074_ThrowChessPiecesProblem.java 5KB
Code_BestArrange.java 5KB
Code_0109_SnakeGame.java 5KB
Code_Dinic.java 5KB
共 617 条
- 1
- 2
- 3
- 4
- 5
- 6
- 7
资源评论
极致人生-010
- 粉丝: 2902
- 资源: 2822
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功