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 \ 5The above binary tree is serialized as
"{1,2,3,#,#,4,#,#,5}"
.A:
------------in-Order search--- and find the two that are not ordered.-------------------
----------------哎,找到之后, 交换值和字节点的值就是了。 ----------非要找parent节点干啥???-----------想不开---------------------------------
由于对于balanced tree, 每个节点找其pre 和next node, 总的复杂度还是 O(n),因此,代码如下。
public class Solution { TreeNode[] swap2; public void recoverTree(TreeNode root) { helper(root); // swap the values of the two node int tmp = swap2[0].val; swap2[0].val = swap2[1].val; swap2[1].val = tmp; } private void helper(TreeNode root){ if(root ==null) return; helper(root.left); TreeNode preNode=null, nextNode=null; if(root.left != null) preNode = getMax(root.left); if(root.right != null) nextNode = getMin(root.right); if(preNode != null && preNode.val > root.val){ if(swap2 == null){ swap2 = new TreeNode[2]; swap2[0] = preNode; } swap2[1] = root; } if(nextNode != null && root.val > nextNode.val){ if(swap2 == null){ swap2 = new TreeNode[2]; swap2[0] = root; } swap2[1] = nextNode; } helper(root.right); } private TreeNode getMin(TreeNode root) { // get the minimum value of a tree while(root!=null && root.left != null) root = root.left; return root; } private TreeNode getMax(TreeNode root) { // get a maximum value of a tree while(root != null && root.right!=null) root = root.right; return root; } }
另外,由于错误2 的原因,是因为我们用了 static.因此,在我们真正实现的时候,我们用了 swap2[] 数组,作为参数来记录更改的变量。
Mistakes:1: 当收入的inoerder list 为: 1 4 3 2 5 6 的时候,如果我们仅仅是两两比较, 就会首先记录 4 3 ;
然后查看3 ,2 记录下了3。 可是,这个时候,我们需要记录的是 2.
方法是: 当已经找到第一个的时候,我们就应该找第二个的时候,就要找后面的那个。因此,对比3,2的时候,我们就应该记录2.
2: ?????下面这个,估计是leetcode的编译错误。
Input: | {2,#,1} |
Output: | {2,#,0} |
Expected: | {1,#,2} |
3: 对于 root 和right 的对比, 应该先比较root 和first of root.right,来建设swap2[] 数组。
Learned:
----------------------------利用同样的思路, 但是,利用同一个地址的引用,我们可以把代码精简如下------------其实就是把一个root节点的前后的对比,巧妙地分成了利用preNode的一个对比。
public class Solution { TreeNode preNode = null; public void recoverTree(TreeNode root) { // use in-order traverse TreeNode[] swap2 = new TreeNode[2]; // use recursively in-order, // remember the places that lastAdded.val>curNode.val inOrder(root, swap2); // swap value int tmp = swap2[0].val; swap2[0].val = swap2[1].val; swap2[1].val = tmp; } private void inOrder(TreeNode root, TreeNode[] swap2) { if (root == null) return; inOrder(root.left, swap2); // the preNode would be changed --- // to last node of root.left if (preNode != null && preNode.val > root.val) { if (swap2[0] == null) swap2[0] = preNode; swap2[1] = root; } preNode = root; inOrder(root.right, swap2); } }错误:
1: (不知道为什么???哈哈,别逗了,Tiger, BS 你),
preNode如果作为函数传递的话,是不对的。必须得作为向量。
---------------------------------3 rd pass---------
public class Solution { static TreeNode justPrinted ,node1=null, node2 = null; public void recoverTree(TreeNode root) { inOrder(root); int tmp = node1.val; node1.val = node2.val; node2.val = tmp; } private void inOrder(TreeNode root){ if(root == null) return ; inOrder(root.left); if(justPrinted !=null && justPrinted.val>root.val){ if(node1==null) node1 = justPrinted; node2 = root; } justPrinted = root; inOrder(root.right); } }
-----------------上面的代码是会报错的, 但只需要把第二行的 static 去掉,就可以了。 不知道为什么?
No comments:
Post a Comment