首页 > 代码库 > leetcode 99 Recover Binary Search Tree ----- java
leetcode 99 Recover Binary Search Tree ----- java
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?
给定一个排序二叉树,然后任意交换了其中两个节点,要求在使用常数个空间和不改变结构的前提下恢复原来的二叉树。
如果用O(n)的空间复杂度,那么直接中序遍历就好了,现在用常数个,那么只需要记录两次就好了,中序遍历的时候,需要动动脑子。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { TreeNode pre; TreeNode first; TreeNode second; public void inorder(TreeNode root){ if(root == null){ return; } inorder(root.left); if(pre == null){ pre = root; }else{ if(pre.val > root.val){ if(first == null){ first = pre; } second = root; } pre = root; } inorder(root.right); } public void recoverTree(TreeNode root) { pre = null; first = null; second = null; inorder(root); if(first!=null && second!=null){ int tmp = first.val; first.val = second.val; second.val = tmp; } } }
leetcode 99 Recover Binary Search Tree ----- java
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。