2020-4-26

617076674 · 617076674 · commit 615ebf464583 · 2020-04-26T11:15:08.000+08:00
diff --git a/question0663_equal_tree_partition/Solution.java b/question0663_equal_tree_partition/Solution.java
@@ -0,0 +1,36 @@
+package question0663_equal_tree_partition;
+
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * 如果树中所有节点的和 total 是一个奇数，显然无法去掉一条边将其分成两颗节点和相同的子树。
+ *
+ * 如果树中所有节点的和 total 是一个偶数，去寻找一颗子树（不包括原树本身），该子树的节点和为 total 的一半。
+ *
+ * 时间复杂度和空间复杂度均是O(n)，其中n为树中的节点个数。
+ *
+ * 执行用时：3ms，击败59.09%。消耗内存：40.9MB，击败100.00%
+ */
+public class Solution {
+    private Set<Integer> set = new HashSet<>();
+
+    public boolean checkEqualTree(TreeNode root) {
+        int total = sum(root, root);
+        if ((total & 1) == 1) {
+            return false;
+        }
+        return set.contains(total >> 1);
+    }
+
+    private int sum(TreeNode treeNode, TreeNode root) {
+        if (null == treeNode) {
+            return 0;
+        }
+        int result = treeNode.val + sum(treeNode.left, root) + sum(treeNode.right, root);
+        if (treeNode != root) {
+            set.add(result);
+        }
+        return result;
+    }
+}
diff --git a/question0663_equal_tree_partition/TreeNode.java b/question0663_equal_tree_partition/TreeNode.java
@@ -0,0 +1,13 @@
+package question0663_equal_tree_partition;
+
+public class TreeNode {
+    int val;
+
+    TreeNode left;
+
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
diff --git a/question0742_closest_leaf_in_a_binary_tree/Solution.java b/question0742_closest_leaf_in_a_binary_tree/Solution.java
@@ -0,0 +1,60 @@
+package question0742_closest_leaf_in_a_binary_tree;
+
+import java.util.*;
+
+/**
+ * 将树转化为图，再广搜。
+ *
+ * 时间复杂度和空间复杂度均是O(n)，其中n为树中的节点个数。
+ *
+ * 执行用时：7ms，击败40.82%。消耗内存：39.6MB，击败100.00%。
+ */
+public class Solution {
+    public int findClosestLeaf(TreeNode root, int k) {
+        if (root.left == null && root.right == null) {
+            return k;
+        }
+        List<Integer>[] graph = new List[1001];
+        for (int i = 0; i < graph.length; i++) {
+            graph[i] = new ArrayList<>();
+        }
+        Queue<TreeNode> queue1 = new LinkedList<>();
+        queue1.add(root);
+        boolean[] isLeaf = new boolean[1001];
+        while (!queue1.isEmpty()) {
+            TreeNode now = queue1.poll();
+            if (now.left == null && now.right == null) {
+                isLeaf[now.val] = true;
+            }
+            if (now.left != null) {
+                graph[now.val].add(now.left.val);
+                graph[now.left.val].add(now.val);
+                queue1.add(now.left);
+            }
+            if (now.right != null) {
+                graph[now.val].add(now.right.val);
+                graph[now.right.val].add(now.val);
+                queue1.add(now.right);
+            }
+        }
+        Queue<Integer> queue2 = new LinkedList<>();
+        queue2.add(k);
+        boolean[] visited = new boolean[1001];
+        while (!queue2.isEmpty()) {
+            int qSize = queue2.size();
+            for (int i = 0; i < qSize; i++) {
+                int now = queue2.poll();
+                visited[now] = true;
+                if (isLeaf[now]) {
+                    return now;
+                }
+                for (int j = 0; j < graph[now].size(); j++) {
+                    if (!visited[graph[now].get(j)]) {
+                        queue2.add(graph[now].get(j));
+                    }
+                }
+            }
+        }
+        return -1;
+    }
+}
diff --git a/question0742_closest_leaf_in_a_binary_tree/TreeNode.java b/question0742_closest_leaf_in_a_binary_tree/TreeNode.java
@@ -0,0 +1,13 @@
+package question0742_closest_leaf_in_a_binary_tree;
+
+public class TreeNode {
+    int val;
+
+    TreeNode left;
+
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
diff --git a/question0776_split_bst/Solution.java b/question0776_split_bst/Solution.java
@@ -0,0 +1,24 @@
+package question0776_split_bst;
+
+/**
+ * 执行用时：0ms，击败100.00%。消耗内存：37.6MB，击败100.00%。
+ */
+public class Solution {
+    public TreeNode[] splitBST(TreeNode root, int V) {
+        if (null == root) {
+            return new TreeNode[] {null, null};
+        }
+        if (root.val == V) {
+            TreeNode treeNode = root.right;
+            root.right = null;
+            return new TreeNode[] {root, treeNode};
+        } else if (root.val > V) {
+            TreeNode[] leftResult = splitBST(root.left, V);
+            root.left = leftResult[1];
+            return new TreeNode[] {leftResult[0], root};
+        }
+        TreeNode[] rightResult = splitBST(root.right, V);
+        root.right = rightResult[0];
+        return new TreeNode[] {root, rightResult[1]};
+    }
+}
diff --git a/question0776_split_bst/TreeNode.java b/question0776_split_bst/TreeNode.java
@@ -0,0 +1,13 @@
+package question0776_split_bst;
+
+public class TreeNode {
+    int val;
+
+    TreeNode left;
+
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
