2020-4-18

617076674 · 617076674 · commit 5ddf87159084 · 2020-04-18T09:11:32.000+08:00
diff --git a/lcci0403_list_of_depth/ListNode.java b/lcci0403_list_of_depth/ListNode.java
@@ -0,0 +1,11 @@
+package lcci0403_list_of_depth;
+
+public class ListNode {
+    int val;
+
+    ListNode next;
+
+    ListNode(int x) {
+        val = x;
+    }
+}
diff --git a/lcci0403_list_of_depth/Solution.java b/lcci0403_list_of_depth/Solution.java
@@ -0,0 +1,45 @@
+package lcci0403_list_of_depth;
+
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+
+/**
+ * 层序遍历。
+ *
+ * 时间复杂度和空间复杂度均是O(n)，其中n为树中的节点个数。
+ *
+ * 执行用时：1ms，击败98.68%。消耗内存：37.9MB，击败100.00%。
+ */
+public class Solution {
+    public ListNode[] listOfDepth(TreeNode tree) {
+        if (null == tree) {
+            return new ListNode[0];
+        }
+        List<ListNode> list = new ArrayList<>();
+        Queue<TreeNode> queue = new LinkedList<>();
+        queue.add(tree);
+        while (!queue.isEmpty()) {
+            int qSize = queue.size();
+            ListNode dummyHead = new ListNode(-1), cur = dummyHead;
+            for (int i = 0; i < qSize; i++) {
+                TreeNode now = queue.poll();
+                cur.next = new ListNode(now.val);
+                cur = cur.next;
+                if (null != now.left) {
+                    queue.add(now.left);
+                }
+                if (null != now.right) {
+                    queue.add(now.right);
+                }
+            }
+            list.add(dummyHead.next);
+        }
+        ListNode[] result = new ListNode[list.size()];
+        for (int i = 0; i < result.length; i++) {
+            result[i] = list.get(i);
+        }
+        return result;
+    }
+}
diff --git a/lcci0403_list_of_depth/TreeNode.java b/lcci0403_list_of_depth/TreeNode.java
@@ -0,0 +1,13 @@
+package lcci0403_list_of_depth;
+
+public class TreeNode {
+    int val;
+
+    TreeNode left;
+
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
diff --git a/lcci0405_legal_binary_search_tree/Solution.java b/lcci0405_legal_binary_search_tree/Solution.java
@@ -0,0 +1,32 @@
+package lcci0405_legal_binary_search_tree;
+
+/**
+ * 中序遍历。
+ *
+ * 时间复杂度和空间复杂度均是O(n)，其中n为树中的节点个数。
+ *
+ * 执行用时：0ms，击败100.00%。消耗内存：39.4MB，击败100.00%。
+ */
+public class Solution {
+    private Integer pre;
+
+    private boolean result = true;
+
+    public boolean isValidBST(TreeNode root) {
+        inOrderTraversal(root);
+        return result;
+    }
+
+    private void inOrderTraversal(TreeNode treeNode) {
+        if (null == treeNode || !result) {
+            return;
+        }
+        inOrderTraversal(treeNode.left);
+        if (pre != null && treeNode.val <= pre) {
+            result = false;
+            return;
+        }
+        pre = treeNode.val;
+        inOrderTraversal(treeNode.right);
+    }
+}
diff --git a/lcci0405_legal_binary_search_tree/TreeNode.java b/lcci0405_legal_binary_search_tree/TreeNode.java
@@ -0,0 +1,13 @@
+package lcci0405_legal_binary_search_tree;
+
+public class TreeNode {
+    int val;
+
+    TreeNode left;
+
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
diff --git a/lcci0406_successor/Solution.java b/lcci0406_successor/Solution.java
@@ -0,0 +1,29 @@
+package lcci0406_successor;
+
+/**
+ * 中序遍历。
+ *
+ * 时间复杂度和空间复杂度均是O(n)，其中n为树中的节点个数。
+ *
+ * 执行用时：3ms，击败100.00%。消耗内存：40.2MB，击败100.00%。
+ */
+public class Solution {
+    private TreeNode pre, result;
+
+    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
+        inOrderTraversal(root, p);
+        return result;
+    }
+
+    private void inOrderTraversal(TreeNode treeNode, TreeNode p) {
+        if (null == treeNode || null != result) {
+            return;
+        }
+        inOrderTraversal(treeNode.left, p);
+        if (pre == p) {
+            result = treeNode;
+        }
+        pre = treeNode;
+        inOrderTraversal(treeNode.right, p);
+    }
+}
diff --git a/lcci0406_successor/TreeNode.java b/lcci0406_successor/TreeNode.java
@@ -0,0 +1,13 @@
+package lcci0406_successor;
+
+public class TreeNode {
+    int val;
+
+    TreeNode left;
+
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
