验证二叉树 二叉树的公共祖先

chenweijie · chenweijie · commit 1835ab13898a · 2020-08-30T23:30:39.000+08:00
diff --git a/src/main/java/com/chen/algorithm/study/test235/Solution.java b/src/main/java/com/chen/algorithm/study/test235/Solution.java
@@ -0,0 +1,32 @@
+package com.chen.algorithm.study.test235;
+
+/**
+ * @author :  chen weijie
+ * @Date: 2020-08-30 23:13
+ */
+public class Solution {
+
+
+    class TreeNode {
+        int val;
+        TreeNode left;
+        TreeNode right;
+
+        TreeNode(int x) {
+            val = x;
+        }
+    }
+
+    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+
+        if (p.val < root.val && q.val < root.val) {
+            return lowestCommonAncestor(root.left, p, q);
+        }
+
+        if (p.val > root.val && q.val > root.val) {
+            return lowestCommonAncestor(root.right, p, q);
+        }
+
+        return root;
+    }
+}
diff --git a/src/main/java/com/chen/algorithm/study/test235/Solution2.java b/src/main/java/com/chen/algorithm/study/test235/Solution2.java
@@ -0,0 +1,35 @@
+package com.chen.algorithm.study.test235;
+
+/**
+ * @author :  chen weijie
+ * @Date: 2020-08-30 23:02
+ */
+public class Solution2 {
+
+    class TreeNode {
+        int val;
+        TreeNode left;
+        TreeNode right;
+
+        TreeNode(int x) {
+            val = x;
+        }
+    }
+
+    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+
+        while (root != null) {
+
+            if (p.val < root.val && q.val < root.val) {
+                root = root.left;
+            } else if (p.val > root.val && q.val > root.val) {
+                root = root.right;
+            } else {
+                return root;
+            }
+        }
+        return root;
+    }
+
+
+}
diff --git a/src/main/java/com/chen/algorithm/study/test236/Solution.java b/src/main/java/com/chen/algorithm/study/test236/Solution.java
@@ -0,0 +1,44 @@
+package com.chen.algorithm.study.test236;
+
+/**
+ * @author :  chen weijie
+ * @Date: 2020-08-30 23:02
+ */
+public class Solution {
+
+    class TreeNode {
+        int val;
+        TreeNode left;
+        TreeNode right;
+
+        TreeNode(int x) {
+            val = x;
+        }
+    }
+
+    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+
+        if (root == null) {
+            return root;
+        }
+
+        if (root == p || root == q) {
+            return root;
+        }
+
+        TreeNode left = lowestCommonAncestor(root.left, p, q);
+        TreeNode right = lowestCommonAncestor(root.right, p, q);
+
+        if (left == null) {
+            return right;
+        }
+
+        if (right == null) {
+            return left;
+        }
+
+        return root;
+    }
+
+
+}
diff --git a/src/main/java/com/chen/algorithm/study/test98/Solution.java b/src/main/java/com/chen/algorithm/study/test98/Solution.java
@@ -0,0 +1,48 @@
+package com.chen.algorithm.study.test98;
+
+/**
+ * @author :  chen weijie
+ * @Date: 2020-08-30 18:32
+ */
+public class Solution {
+
+
+    class TreeNode {
+        int val;
+        TreeNode left;
+        TreeNode right;
+
+        TreeNode(int x) {
+            val = x;
+        }
+    }
+
+
+    /**
+     * 要求根节点大于左子树的最大值，小于右子树的最小值
+     *
+     * @param root
+     * @return
+     */
+    public boolean isValidBST(TreeNode root) {
+        return isValid(root, null, null);
+    }
+
+
+    public boolean isValid(TreeNode root, Integer max, Integer min) {
+
+        if (root == null) {
+            return true;
+        }
+        if (min != null && root.val <= min) {
+            return false;
+        }
+        if (max != null && root.val >= max) {
+            return false;
+        }
+
+        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
+    }
+
+
+}
diff --git a/src/main/java/com/chen/algorithm/study/test98/Solution1.java b/src/main/java/com/chen/algorithm/study/test98/Solution1.java
@@ -0,0 +1,61 @@
+package com.chen.algorithm.study.test98;
+
+import java.util.Stack;
+
+/**
+ * @author :  chen weijie
+ * @Date: 2020-08-30 20:54
+ */
+public class Solution1 {
+
+
+    class TreeNode {
+        int val;
+        TreeNode left;
+        TreeNode right;
+
+        TreeNode(int x) {
+            val = x;
+        }
+    }
+
+
+    /**
+     * 要求根节点大于左子树的最大值，小于右子树的最小值
+     *
+     * @param root
+     * @return
+     */
+    public boolean isValidBST(TreeNode root) {
+
+        if (root == null) {
+            return true;
+        }
+
+        Stack<TreeNode> stack = new Stack<>();
+        TreeNode curr = root;
+
+//        int preVal = Integer.MIN_VALUE;
+          double preVal = -Double.MAX_VALUE;
+        while (!stack.isEmpty() || curr != null) {
+            while (curr != null) {
+                stack.push(curr);
+                curr = curr.left;
+            }
+
+            curr = stack.pop();
+            int currVal = curr.val;
+            if (preVal >= currVal) {
+                return false;
+            }
+            preVal = currVal;
+            curr = curr.right;
+        }
+        return true;
+    }
+
+
+
+
+
+}
