leaf similar trees

sherxon · Jul 22, 2018 · 61ec7e8 · 61ec7e8
1 parent 45f81c2
commit 61ec7e8
Show file tree

Hide file tree

Showing 3 changed files with 61 additions and 2 deletions.
diff --git a/src/problems/Easy.txt b/src/problems/Easy.txt
@@ -1266,7 +1266,7 @@ The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2
 Note:
 The range of node's value is in the range of 32-bit signed integer.
 
-118)Convert BST to Greater Tree
+119)Convert BST to Greater Tree
 Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
 
 Example:
@@ -1279,4 +1279,20 @@ Input: The root of a Binary Search Tree like this:
 Output: The root of a Greater Tree like this:
              18
             /   \
-          20     13
+          20     13
+120)Leaf-Similar Trees
+Consider all the leaves of a binary tree.  From left to right order, the values of those leaves form a leaf value sequence.
+
+
+
+For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
+
+Two binary trees are considered leaf-similar if their leaf value sequence is the same.
+
+Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
+
+
+
+Note:
+
+Both of the given trees will have between 1 and 100 nodes.
diff --git a/src/problems/easy/LeafSimilarTrees.java b/src/problems/easy/LeafSimilarTrees.java
@@ -0,0 +1,41 @@
+package problems.easy;
+
+import problems.utils.TreeNode;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Why Did you create this class? what does it do?
+ */
+public class LeafSimilarTrees {
+    public boolean leafSimilar(TreeNode x, TreeNode y) {
+        if (x == null || y == null)
+            return x == y;
+
+        List<Integer> l = new ArrayList<>();
+        List<Integer> l2 = new ArrayList<>();
+        dfs(x, l);
+        dfs(y, l2);
+
+        if (l.size() != l2.size())
+            return false;
+
+        for (int i = 0; i < l.size(); i++) {
+            if (l.get(i) != l2.get(i))
+                return false;
+        }
+        return true;
+    }
+
+    void dfs(TreeNode x, List<Integer> list) {
+        if (x == null)
+            return;
+        if (x.left == null && x.right == null) {
+            list.add(x.val);
+            return;
+        }
+        dfs(x.left, list);
+        dfs(x.right, list);
+    }
+}
diff --git a/src/problems/medium/LongestWordinDictionarythroughDeleting.java b/src/problems/medium/LongestWordinDictionarythroughDeleting.java
@@ -1,5 +1,7 @@
 package problems.medium;
 
+import problems.utils.TreeNode;
+
 import java.util.Collections;
 import java.util.List;