add 1457

fishercoder1534 · fishercoder1534 · commit 92059e4fc4fa · 2020-05-24T07:37:34.000-07:00
diff --git a/README.md b/README.md
@@ -8,7 +8,8 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
-|1456|[ Maximum Number of Vowels in a Substring of Given Length](https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1456.java) | |Easy|String, Sliding Window|
+|1457|[Pseudo-Palindromic Paths in a Binary Tree](https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1457.java) | |Medium|Bit Manipulation, Tree, DFS|
+|1456|[Maximum Number of Vowels in a Substring of Given Length](https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1456.java) | |Medium|String, Sliding Window|
 |1455|[Check If a Word Occurs As a Prefix of Any Word in a Sentence](https://leetcode.com/problems/check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1455.java) | |Easy|String|
 |1452|[People Whose List of Favorite Companies Is Not a Subset of Another List](https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1452.java) | |Medium|String, Sort|
 |1451|[Rearrange Words in a Sentence](https://leetcode.com/problems/rearrange-words-in-a-sentence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1451.java) | |Medium|String, Sort|
diff --git a/src/main/java/com/fishercoder/solutions/_1457.java b/src/main/java/com/fishercoder/solutions/_1457.java
@@ -0,0 +1,58 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.TreeNode;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+public class _1457 {
+    public static class Solution1 {
+        public int pseudoPalindromicPaths(TreeNode root) {
+            List<List<Integer>> allPaths = new ArrayList<>();
+            List<Integer> path = new ArrayList<>();
+            dfs(root, path, allPaths);
+            int result = 0;
+            for (List<Integer> thisPath : allPaths) {
+                Map<Integer, Integer> count = findCount(thisPath);
+                int oddCount = 0;
+                for (int num : count.keySet()) {
+                    if (count.get(num) % 2 != 0) {
+                        oddCount++;
+                    }
+                    if (oddCount > 1) {
+                        break;
+                    }
+                }
+                if (oddCount <= 1) {
+                    result++;
+                }
+            }
+            return result;
+        }
+
+        private void dfs(TreeNode root, List<Integer> path, List<List<Integer>> allPaths) {
+            if (root.left == null && root.right == null) {
+                path.add(root.val);
+                allPaths.add(new ArrayList<>(path));
+                return;
+            }
+            path.add(root.val);
+            if (root.left != null) {
+                dfs(root.left, path, allPaths);
+                path.remove(path.size() - 1);
+            }
+            if (root.right != null) {
+                dfs(root.right, path, allPaths);
+                path.remove(path.size() - 1);
+            }
+        }
+
+        private Map<Integer, Integer> findCount(List<Integer> path) {
+            Map<Integer, Integer> map = new HashMap<>();
+            path.forEach(i -> map.put(i, map.getOrDefault(i, 0) + 1));
+            return map;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1457Test.java b/src/test/java/com/fishercoder/_1457Test.java
@@ -0,0 +1,28 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._1456;
+import com.fishercoder.solutions._1457;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static junit.framework.TestCase.assertEquals;
+
+public class _1457Test {
+    private static _1457.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1457.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(2, 3, 1, 3, 1, null, 1));
+        assertEquals(2, solution1.pseudoPalindromicPaths(root));
+    }
+
+}
