fd

dingjikerbo · dingjikerbo · commit 4ce3026b4aef · 2018-12-09T16:38:37.000+08:00
diff --git a/README.md b/README.md
@@ -380,6 +380,7 @@
 |557|[Reverse Words in a String III](https://leetcode.com/problems/reverse-words-in-a-string-iii/)| [Java](leetcode/solution/src/ReverseWordsInAStringIII.java)|100||
 |560|[Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)| [Java](leetcode/solution/src/SubarraySumEqualsK.java)|70||
 |564|[Find the Closest Palindrome](https://leetcode.com/problems/find-the-closest-palindrome/)|[Java](leetcode/solution/src/FindTheClosestPalindrome.java)|80|此题暴力法即可|
+|572|[Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/)|[Java](leetcode/solution/src/SubtreeOfAnotherTree.java)|80||
 |606|[Construct String from Binary Tree](https://leetcode.com/problems/construct-string-from-binary-tree/)|[Java](leetcode/solution/src/ConstructStringFromBinaryTree.java)|90||
 |617|[Merge Two Binary Trees](https://leetcode.com/problems/merge-two-binary-trees/)|[Java](leetcode/solution/src/MergeTwoBinaryTrees.java)|100|很简单|
 |621|[Task Scheduler](https://leetcode.com/problems/task-scheduler/)|[Java](leetcode/solution/src/TaskScheduler.java)|70||
diff --git a/leetcode/solution/src/SubtreeOfAnotherTree.java b/leetcode/solution/src/SubtreeOfAnotherTree.java
@@ -0,0 +1,19 @@
+public class SubtreeOfAnotherTree {
+
+    /**
+     * 非递归的办法是拼成字符串，看是否是子串
+     */
+    public boolean isSubtree(TreeNode s, TreeNode t) {
+        return isEqual(s, t) || (s != null && (isSubtree(s.left, t) || isSubtree(s.right, t)));
+    }
+
+    private boolean isEqual(TreeNode s, TreeNode t) {
+        if (t == null && s == null) {
+            return true;
+        }
+        if (t == null || s == null) {
+            return false;
+        }
+        return s.val == t.val && isEqual(s.left, t.left) && isEqual(s.right, t.right);
+    }
+}
diff --git a/leetcode/src/Main.java b/leetcode/src/Main.java
@@ -6,27 +6,18 @@ public class Main {
 
     public static class Solution {
 
-        public List<List<Integer>> pathSum(TreeNode root, int sum) {
-            List<List<Integer>> result = new ArrayList<>();
-            helpr(root, sum, new ArrayList<>(), result);
-            return result;
+        public boolean isSubtree(TreeNode s, TreeNode t) {
+            return isEqual(s, t) || (s != null && (isSubtree(s.left, t) || isSubtree(s.right, t)));
         }
 
-        private void helpr(TreeNode root, int sum, List<Integer> list, List<List<Integer>> result) {
-            if (root == null) {
-                return;
+        private boolean isEqual(TreeNode s, TreeNode t) {
+            if (t == null && s == null) {
+                return true;
             }
-
-            list.add(root.val);
-
-            if (root.left == null && root.right == null && root.val == sum) {
-                result.add(new ArrayList<>(list));
-            } else {
-                helpr(root.left, sum - root.val, list, result);
-                helpr(root.right, sum - root.val, list, result);
+            if (t == null || s == null) {
+                return false;
             }
-
-            list.remove(list.size() - 1);
+            return s.val == t.val && isEqual(s.left, t.left) && isEqual(s.right, t.right);
         }
     }
 
