Merge pull request algorithm004-01#365 from pauleyliu/master

melody-li · web-flow · commit 548a8b8fbdad · 2019-10-28T12:08:22.000+08:00
551_Week 02
diff --git a/Week 02/id_551/LeetCode_104_551.recursion.swift b/Week 02/id_551/LeetCode_104_551.recursion.swift
@@ -0,0 +1,22 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     public var val: Int
+ *     public var left: TreeNode?
+ *     public var right: TreeNode?
+ *     public init(_ val: Int) {
+ *         self.val = val
+ *         self.left = nil
+ *         self.right = nil
+ *     }
+ * }
+ */
+class Solution {
+    func maxDepth(_ root: TreeNode?) -> Int {
+        guard let r = root else { return 0 }
+        // handle exponentially more recursive call to null root nodes
+        let l_h = (r.left == nil) ? 0 : maxDepth(r.left)
+        let r_h = (r.right == nil) ? 0 : maxDepth(r.right)
+        return (l_h > r_h ? l_h : r_h) + 1
+    }
+}
diff --git a/Week 02/id_551/LeetCode_111_551.swift b/Week 02/id_551/LeetCode_111_551.swift
@@ -0,0 +1,29 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     public var val: Int
+ *     public var left: TreeNode?
+ *     public var right: TreeNode?
+ *     public init(_ val: Int) {
+ *         self.val = val
+ *         self.left = nil
+ *         self.right = nil
+ *     }
+ * }
+ */
+class Solution {
+    func minDepth(_ root: TreeNode?) -> Int {
+        guard let r = root else { return 0 }
+        
+        let left_h = minDepth(r.left)
+        let right_h = minDepth(r.right)
+        
+        if r.left == nil || r.right == nil {
+            // leaf node、left null right node、right null left node
+            // 0 0, 0 r_h, l_h 0
+            return left_h + right_h + 1
+        } else {
+            return (left_h > right_h ? right_h : left_h) + 1
+        }
+    }
+}
diff --git a/Week 02/id_551/LeetCode_226_551.py b/Week 02/id_551/LeetCode_226_551.py
@@ -0,0 +1,12 @@
+# Definition for a binary tree node.
+# class TreeNode:
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Solution:
+    def invertTree(self, root: TreeNode) -> TreeNode:
+        if root is not None:
+            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
+            return root
diff --git a/Week 02/id_551/LeetCode_226_551.swift b/Week 02/id_551/LeetCode_226_551.swift
@@ -0,0 +1,19 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     public var val: Int
+ *     public var left: TreeNode?
+ *     public var right: TreeNode?
+ *     public init(_ val: Int) {
+ *         self.val = val
+ *         self.left = nil
+ *         self.right = nil
+ *     }
+ * }
+ */
+class Solution {
+    func invertTree(_ root: TreeNode?) -> TreeNode? {
+        if let r = root { (r.left, r.right) = (invertTree(r.right), invertTree(r.left)) }
+        return root
+    }
+}
diff --git a/Week 02/id_551/LeetCode_70_551.dp.swift b/Week 02/id_551/LeetCode_70_551.dp.swift
@@ -0,0 +1,15 @@
+iclass Solution {
+    func climbStairs(_ n: Int) -> Int {
+        if n <= 1 { return 1 }
+        
+        var dp: [Int] = Array(repeating: 0, count: n + 1)
+        dp[0] = 1
+        dp[1] = 1
+
+        for i in 2...n {
+            dp[i] = dp[i-1] + dp[i-2]
+        }
+    
+        return dp[n]
+    }
+}
diff --git a/Week 02/id_551/LeetCode_70_551.recursion_cache.swift b/Week 02/id_551/LeetCode_70_551.recursion_cache.swift
@@ -0,0 +1,17 @@
+class Solution {
+    
+    var cache = [Int: Int]()
+    func climbStairs(_ n: Int) -> Int {
+
+        if n <= 1 { return 1 }
+
+        if let val = cache[n] {
+            return val
+        } else {
+            cache[n] = climbStairs(n - 1) + climbStairs(n - 2)
+            return cache[n]!
+        }
+
+    }
+    
+}
diff --git a/Week 02/id_551/LeetCode_98_551.swift b/Week 02/id_551/LeetCode_98_551.swift
@@ -0,0 +1,38 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     public var val: Int
+ *     public var left: TreeNode?
+ *     public var right: TreeNode?
+ *     public init(_ val: Int) {
+ *         self.val = val
+ *         self.left = nil
+ *         self.right = nil
+ *     }
+ * }
+ */
+class Solution {
+    func isValidBST(_ root: TreeNode?) -> Bool {
+       
+        // recursion func
+        func isValid(_ root: TreeNode?, lower: Int = Int.min, higher: Int = Int.max) -> Bool {
+           
+            // recursion terminator
+            guard let r = root else { return true }
+            
+            // process current level
+            if r.val <= lower || r.val >= higher { return false }
+            
+            // drill down (boundary convergence)
+            if !isValid(r.left, lower: lower, higher: r.val) { return false }
+            if !isValid(r.right, lower: r.val, higher: higher) { return false }
+            
+            return true
+        }  
+        
+        return isValid(root)
+    }
+}
+
+
+
