fd

dingjikerbo · dingjikerbo · commit 21a083bb48d5 · 2017-12-05T21:45:42.000+08:00
diff --git a/solution/src/main/java/com/inuker/solution/RecoverBinarySearchTree.java b/solution/src/main/java/com/inuker/solution/RecoverBinarySearchTree.java
@@ -10,106 +10,50 @@
 
 public class RecoverBinarySearchTree {
 
-    private TreeNode first, second, prev;
+    TreeNode first, second, prev;
 
-    /**
-     * TestCase
-     * [0, 1]是最重要且易错的
-     */
     public void recoverTree(TreeNode root) {
-        if (root == null) {
-            return;
-        }
-        inorderTraversal(root);
-        int t = first.val;
+        inorder(root);
+        int val = first.val;
         first.val = second.val;
-        second.val = t;
+        second.val = val;
     }
 
-    // 首先first是可以一次性确定的，second不能，可能要被多次覆盖，所以
-    // 下面设置了second后没有立即终止，而是继续遍历，直到最后的那个才是真正的
-    private void inorderTraversal(TreeNode node) {
-        if (node == null) {
-            return;
-        }
-
-        inorderTraversal(node.left);
-
-        if (prev != null) {
-            // 两个节点交换，肯定是大的放前面了，小的放后面了，所以遇到的第一个prev大于node的，first肯定是prev.
-            // 遇到的第一个node小于prev的，second肯定是node
-            if (first == null && prev.val > node.val) {
-                first = prev;
-            }
-
-            // 这里可否换成second == null，不能，因为second要多次覆盖
-            if (first != null && prev.val > node.val) {
-                second = node;
-                // 这里可否加上break
+    private void inorder(TreeNode root) {
+        while (root != null) {
+            if (root.left == null) {
+                detect(root);
+                root = root.right;
+            } else {
+                TreeNode pre = root.left;
+                for ( ; pre.right != null && pre.right != root; pre = pre.right);
+                if (pre.right == null) {
+                    pre.right = root;
+                    root = root.left;
+                } else {
+                    pre.right = null;
+                    detect(root);
+                    root = root.right;
+                }
             }
-
-            // 以上两个if为何可能同时满足，参考[0,1]
         }
-
-        prev = node;
-
-        inorderTraversal(node.right);
     }
 
-
-    // 可换成非递归的写法
-    private void inorderTraverse(TreeNode root) {
+    private void inorder2(TreeNode root) {
         Stack<TreeNode> stack = new Stack<>();
-
         while (!stack.isEmpty() || root != null) {
             if (root != null) {
                 stack.push(root);
                 root = root.left;
             } else {
                 root = stack.pop();
-
-                if (prev != null) {
-                    if (first == null && root.val < prev.val) {
-                        first = prev;
-                    }
-
-                    if (first != null && root.val < prev.val) {
-                        second = root;
-                    }
-                }
-
-                prev = root;
-
-                root = root.right;
-            }
-        }
-    }
-
-    private void inorderTraverse2(TreeNode root) {
-        TreeNode temp;
-
-        while (root != null) {
-            if (root.left == null) {
-                helper(root);
+                detect(root);
                 root = root.right;
-            } else {
-                temp = root.left;
-                while (temp.right != null && temp.right != root) {
-                    temp = temp.right;
-                }
-                if (temp.right == null) {
-                    temp.right = root;
-                    root = root.left;
-                } else {
-                    temp.right = null;
-                    helper(root);
-                    root = root.right;
-                }
             }
         }
     }
 
-    private void helper(TreeNode node) {
+    private void detect(TreeNode node) {
         if (prev != null) {
             if (first == null && prev.val > node.val) {
                 first = prev;
diff --git a/test/src/main/java/com/inuker/test/main.java b/test/src/main/java/com/inuker/test/main.java
@@ -1,5 +1,7 @@
 package com.inuker.test;
 
+import com.leetcode.library.TreeNode;
+
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
@@ -22,17 +24,5 @@ public static void main(String[] args) {
 
     }
 
-    public boolean validWordSquare(List<String> words) {
-        for (int i = 0; i < words.size(); i++) {
-            for (int j = 0; j < words.get(i).length(); j++) {
-                if (j >= words.size() || i >= words.get(j).length()) {
-                    return false;
-                }
-                if (words.get(i).charAt(j) != words.get(j).charAt(i)) {
-                    return false;
-                }
-            }
-        }
-        return true;
-    }
+
 }
