首页 > 代码库 > [leetcode] Recover Binary Search Tree
[leetcode] Recover Binary Search Tree
题目：（Tree ，DFS）
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.
题解：
还是和inorder 遍历联系在一起的，在遍历的时候记录两个被交换的值
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { TreeNode maxfinal=new TreeNode(Integer.MIN_VALUE); TreeNode minfinal=new TreeNode(Integer.MAX_VALUE); public void recoverTree(TreeNode root) { TreeNode min=new TreeNode(Integer.MIN_VALUE); TreeNode max=new TreeNode(Integer.MAX_VALUE); check(root.left,min,root); check(root.right,root,max); int temp=maxfinal.val; maxfinal.val=minfinal.val; minfinal.val=temp; } public void check(TreeNode root,TreeNode min ,TreeNode max){ if(root==null) return ; if(root.val<min.val) { if(minfinal.val>root.val) minfinal=root; if(maxfinal.val<min.val) maxfinal=min; }else if(root.val>max.val) { if(minfinal.val>max.val) minfinal=max; if(maxfinal.val<root.val) maxfinal=root; } check(root.left,min,root); check(root.right,root,max); }}
[leetcode] Recover Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。