本文共 1793 字,大约阅读时间需要 5 分钟。
*
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.
*
public class Solution { TreeNode pre; TreeNode first; TreeNode second; public void recoverTree(TreeNode root) { pre=null;first=null;second=null; inorder(root); if (first!=null){ if (second==null)second=pre; int tmp= first.val; first.val=second.val; second.val=tmp; } } public void inorder (TreeNode root){ if (root==null) return; if (root.left!=null) inorder(root.left); if (pre!=null){ if (first==null && pre.val>root.val) first=pre; else if(first!=null && root.val>first.val ) second=pre; if (first!=null && second!=null) return; } pre=root; if (root.right!=null) inorder(root.right); }}
代码基本大同小异,上次 通过是1年5个月前的事,前两天笔试出了这个题又不会做了,拿出来复习一下。
1。首先碰见搜索二叉树肯定是中序遍历,中序遍历后是个有序有序,所以可以找出哪些节点有冲突。
在找的时候,需要加一个pre指针。 这个用法还挺实用的,把一颗二叉树转换成循环链表 也要加上这个pre指针。
2。就是找到冲突节点时候怎么处理。
所以判定 当有Pre 节点是 和pre节点比较值得大小,如果有冲突,看是第一对冲突节点和第二对冲突节点。只找到一对冲突节点,那就返回这一对,所以有
if(pre!=null && pre.val>root.val){if(first==null){//找到第一队冲突节点 first=pre; second=root;}else{//直接确认第二个冲突节点是第二对的第二个。second=root;}
所以所以前写的代码还是有点问题的,当时不知道怎么过的。。。。
转载地址:http://dvdqi.baihongyu.com/