0112 new algo added.

liuyubobobo · liuyubobobo · commit 432fe73dc464 · 2018-11-17T21:09:05.000-08:00
diff --git a/0112-Path-Sum/cpp-0112/CMakeLists.txt b/0112-Path-Sum/cpp-0112/CMakeLists.txt
@@ -3,5 +3,5 @@ project(cpp_0112)
 
 set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
 
-set(SOURCE_FILES main.cpp)
+set(SOURCE_FILES main2.cpp)
 add_executable(cpp_0112 ${SOURCE_FILES})
diff --git a/0112-Path-Sum/cpp-0112/main.cpp b/0112-Path-Sum/cpp-0112/main.cpp
@@ -14,24 +14,26 @@ struct TreeNode {
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
 
+
 /// Recursive
 /// Time Complexity: O(n), where n is the nodes' number of the tree
 /// Space Complexity: O(h), where h is the height of the tree
 class Solution {
 public:
     bool hasPathSum(TreeNode* root, int sum) {
 
-        if(root == NULL)
+        if(!root)
             return false;
 
-        if(root->left == NULL && root->right == NULL)
+        if(!root->left && !root->right)
             return sum == root->val;
 
         return hasPathSum(root->left, sum - root->val)
                 || hasPathSum(root->right, sum - root->val);
     }
 };
 
+
 int main() {
 
     return 0;
diff --git a/0112-Path-Sum/cpp-0112/main2.cpp b/0112-Path-Sum/cpp-0112/main2.cpp
@@ -0,0 +1,54 @@
+/// Source : https://leetcode.com/problems/path-sum/description/
+/// Author : liuyubobobo
+/// Time   : 2018-11-17
+
+#include <iostream>
+#include <stack>
+
+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
+/// Using Stack
+///
+/// Time Complexity: O(n), where n is the nodes' number of the tree
+/// Space Complexity: O(h), where h is the height of the tree
+class Solution {
+public:
+    bool hasPathSum(TreeNode* root, int sum) {
+
+        if(!root)
+            return false;
+
+        stack<pair<TreeNode*, int>> stack;
+        stack.push(make_pair(root, sum));
+        while(!stack.empty()){
+            TreeNode* cur = stack.top().first;
+            int num = stack.top().second;
+            stack.pop();
+
+            if(num == cur->val && !cur->left && !cur->right)
+                return true;
+
+            if (cur->left)
+                stack.push(make_pair(cur->left, num - cur->val));
+            if (cur->right)
+                stack.push(make_pair(cur->right, num - cur->val));
+        }
+        return false;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/0112-Path-Sum/java-0112/src/Solution.java b/0112-Path-Sum/java-0112/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 boolean hasPathSum(TreeNode root, int sum) {
 
         if(root == null)
diff --git a/0112-Path-Sum/java-0112/src/Solution2.java b/0112-Path-Sum/java-0112/src/Solution2.java
@@ -0,0 +1,37 @@
+/// Source : https://leetcode.com/problems/path-sum/description/
+/// Author : liuyubobobo
+/// Time   : 2018-11-17
+
+import java.util.Stack;
+import javafx.util.Pair;
+
+/// Non-Recursive
+/// Using Stack
+///
+/// Time Complexity: O(n), where n is the nodes' number of the tree
+/// Space Complexity: O(h), where h is the height of the tree
+public class Solution2 {
+
+    public boolean hasPathSum(TreeNode root, int sum) {
+
+        if(root == null)
+            return false;
+
+        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
+        stack.push(new Pair<>(root, sum));
+        while(!stack.empty()){
+            TreeNode cur = stack.peek().getKey();
+            int num = stack.peek().getValue();
+            stack.pop();
+
+            if(num == cur.val && cur.left == null && cur.right == null)
+                return true;
+
+            if(cur.left != null)
+                stack.push(new Pair<>(cur.left, num - cur.val));
+            if(cur.right != null)
+                stack.push(new Pair<>(cur.right, num - cur.val));
+        }
+        return false;
+    }
+}
diff --git a/0112-Path-Sum/java-0112/src/TreeNode.java b/0112-Path-Sum/java-0112/src/TreeNode.java
@@ -0,0 +1,7 @@
+// Definition for a binary tree node.
+public class TreeNode {
+    int val;
+    TreeNode left;
+    TreeNode right;
+    TreeNode(int x) { val = x; }
+}
diff --git a/readme.md b/readme.md
@@ -141,7 +141,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 109 | [Convert Sorted List to Binary Search Tree](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/) | [solution](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/solution/) | [C++](0109-Convert-Sorted-List-to-Binary-Search-Tree/cpp-0109/) | | |
 | | | | | | |
 | 111 | [Minimum Depth of Binary Tree](https://leetcode.com/problems/minimum-depth-of-binary-tree/description/) | [solution](https://leetcode.com/problems/minimum-depth-of-binary-tree/solution/) | [C++](0111-Minimum-Depth-of-Binary-Tree/cpp-0111/) | | |
-| 112 | [Path Sum](https://leetcode.com/problems/path-sum/description/) | [无] | [C++](0112-Path-Sum/cpp-0112/) | [Java](0112-Path-Sum/cpp-0112/src/) | |
+| 112 | [Path Sum](https://leetcode.com/problems/path-sum/description/) | [solution](https://leetcode.com/problems/path-sum/solution/) | [C++](0112-Path-Sum/cpp-0112/) | [Java](0112-Path-Sum/cpp-0112/src/) | |
 | 113 | [Path Sum II](https://leetcode.com/problems/path-sum-ii/description/) | [无] | [C++](0113-Path-Sum-II/cpp-0113/) | | |
 | | | | | | |
 | 115 | [Distinct Subsequences](https://leetcode.com/problems/distinct-subsequences/description/) | [无] | [C++](0115/Distinct-Subsequences/cpp-0115/) | [Java](0115/Distinct-Subsequences/java-0115/) | |
