0235 new algo added.

liuyubobobo · liuyubobobo · commit fb4463178359 · 2018-12-16T17:39:07.000-08:00
diff --git a/0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/cpp-0235/main.cpp b/0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/cpp-0235/main.cpp
@@ -24,10 +24,9 @@ class Solution {
 public:
     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
 
-        assert(p != NULL && q != NULL);
+        assert(!p && !q);
 
-        if(root == NULL)
-            return NULL;
+        if(!root) return root;
 
         if(p->val < root->val && q->val < root->val)
             return lowestCommonAncestor(root->left, p, q);
diff --git a/0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/cpp-0235/main2.cpp b/0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/cpp-0235/main2.cpp
@@ -0,0 +1,46 @@
+/// Source : https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
+/// Author : liuyubobobo
+/// Time   : 2018-12-16
+
+#include <iostream>
+#include <cassert>
+
+using namespace std;
+
+
+/// Definition for a binary tree node.
+struct TreeNode {
+    int val;
+    TreeNode *left;
+    TreeNode *right;
+    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+};
+
+
+/// Non-Recursive
+/// Time Complexity: O(lgn), where n is the node's number of the tree
+/// Space Complexity: O(1)
+class Solution {
+public:
+    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
+
+        if(!root) return root;
+
+        TreeNode* cur = root;
+        while(cur) {
+            if (p->val < cur->val && q->val < cur->val)
+                cur = cur->left;
+            else if (p->val > cur->val && q->val > cur->val)
+                cur = cur->right;
+            else
+                return cur;
+        }
+
+        return NULL;
+    }
+};
+
+int main() {
+
+    return 0;
+}
diff --git a/0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/java-0235/src/Solution.java b/0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/java-0235/src/Solution.java
@@ -7,14 +7,6 @@
 /// Space Complexity: O(h), where h is the height of the tree
 class Solution {
 
-    // Definition for a binary tree node.
-    public class TreeNode {
-        int val;
-        TreeNode left;
-        TreeNode right;
-        TreeNode(int x) { val = x; }
-    }
-
     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 
         if(p == null || q == null)
diff --git a/0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/java-0235/src/Solution2.java b/0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/java-0235/src/Solution2.java
@@ -0,0 +1,26 @@
+/// Source : https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
+/// Author : liuyubobobo
+/// Time   : 2018-12-16
+
+/// Non-Recursive
+/// Time Complexity: O(lgn), where n is the node's number of the tree
+/// Space Complexity: O(1)
+class Solution2 {
+
+    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+
+        if(root == null)
+            return root;
+
+        TreeNode cur = root;
+        while(cur != null){
+            if(p.val < cur.val && q.val < cur.val)
+                cur = cur.left;
+            else if(p.val > cur.val && q.val > cur.val)
+                cur = cur.right;
+            else
+                return cur;
+        }
+        return  null;
+    }
+}
diff --git a/0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/java-0235/src/TreeNode.java b/0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/java-0235/src/TreeNode.java
@@ -0,0 +1,7 @@
+// Definition for a binary tree node.
+class TreeNode {
+    int val;
+    TreeNode left;
+    TreeNode right;
+    TreeNode(int x) { val = x; }
+}
diff --git a/readme.md b/readme.md
@@ -238,7 +238,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 232 | [Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/description/) | [solution](https://leetcode.com/problems/implement-queue-using-stacks/solution/) | [C++](0232-Implement-Queue-using-Stacks/cpp-0232/) | | |
 | | | | | | |
 | 234 | [Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/description/) | [无] | [C++](0234-Palindrome-Linked-List/cpp-0234/) | | |
-| 235 | [Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/) | [无] | [C++](0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/cpp-0235/) | [Java](0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/java-0235/src/) | |
+| 235 | [Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/) | [solution](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/) | [C++](0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/cpp-0235/) | [Java](0235-Lowest-Common-Ancestor-of-a-Binary-Search-Tree/java-0235/src/) | |
 | 236 | [Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/) | [solution](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/)<br/>[缺：非递归解法；LCA问题总结] | [C++](0236-Lowest-Common-Ancestor-of-a-Binary-Tree/cpp-0236/) | | |
 | 237 | [Delete Node in a Linked List](https://leetcode.com/problems/delete-node-in-a-linked-list/description/) | [solution](https://leetcode.com/problems/delete-node-in-a-linked-list/solution/) | [C++](0237-Delete-Node-in-a-Linked-List/cpp-0237/) | [Java](0237-Delete-Node-in-a-Linked-List/java-0237/src/) | |
 | | | | | | |
