Merge pull request algorithm004-01#385 from mrgulc/master

melody-li · web-flow · commit 6626d6ef26bc · 2019-10-28T12:07:43.000+08:00
521 - Week 02
diff --git a/Week 02/id_521/144.二叉树的前序遍历.js b/Week 02/id_521/144.二叉树的前序遍历.js
@@ -0,0 +1,36 @@
+/*
+ * @lc app=leetcode.cn id=144 lang=javascript
+ *
+ * [144] 二叉树的前序遍历
+ */
+
+// @lc code=start
+/**
+ * Definition for a binary tree node.
+ * function TreeNode(val) {
+ *     this.val = val;
+ *     this.left = this.right = null;
+ * }
+ */
+/**
+ * @param {TreeNode} root
+ * @return {number[]}
+ */
+var preorderTraversal = function(root) {
+    let arr = []
+    function helper(root, arr) {
+        if(root !== null){
+            arr.push(root.val); // 处理本层逻辑
+            if(root.left !== null) {
+                helper(root.left, arr) // 进入下一层
+            }
+            if(root.right !== null) { // 进入下一层， 这里其实有点分治的意思，左右分别处理
+                helper(root.right, arr)
+            }
+        } 
+    }
+    helper(root, arr)
+    return arr
+};
+// @lc code=end
+
diff --git a/Week 02/id_521/242.有效的字母异位词.js b/Week 02/id_521/242.有效的字母异位词.js
@@ -0,0 +1,45 @@
+
+/**
+ * @param {string} s
+ * @param {string} t
+ * @return {boolean}
+ * 解法一: 暴力解法; 时间复杂度为O(nlogn) + O(nlogn) = O(nlogn) 
+ */
+var isAnagram = function(s, t) {
+    if(s.length !== t.length) {
+        return false
+    }
+    var s_arr = [...s]
+    var t_arr = [...t]
+    s_arr.sort()
+    t_arr.sort()
+    s = JSON.stringify(s_arr)
+    t = JSON.stringify(t_arr)
+    return s === t
+};
+
+
+/**
+ * @param {string} s
+ * @param {string} t
+ * @return {boolean}
+ * 解法二: 把字符传唤为0-25的数字， 对数字所在数组+-
+ */
+var isAnagram = function(s, t) {
+    if(s.length != t.length) {
+        return false
+    }
+    var arr = new Array(26).fill(0)
+ 
+    for(let i = 0; i < s.length; i++) {
+        arr[s.charCodeAt(i) - 97]++
+        arr[t.charCodeAt(i) - 97]--
+    }
+ 
+    for(let item of arr) {
+        if(item !== 0) {
+            return false
+        }
+    }
+    return true
+ };
diff --git a/Week 02/id_521/429.n叉树的层序遍历.js b/Week 02/id_521/429.n叉树的层序遍历.js
@@ -0,0 +1,40 @@
+/*
+ * @lc app=leetcode.cn id=429 lang=javascript
+ *
+ * [429] N叉树的层序遍历
+ */
+
+// @lc code=start
+/**
+ * // Definition for a Node.
+ * function Node(val,children) {
+ *    this.val = val;
+ *    this.children = children;
+ * };
+ */
+/**
+ * @param {Node} root
+ * @return {number[][]}
+ */
+var levelOrder = function(root) {
+    let arr = []
+    function helper(root, arr, level){
+        if(root === null) {
+            return 
+        }
+        if(arr[level] === undefined) {
+            arr[level] = []
+        }
+        arr[level].push(root.val)
+        if(root.children && root.children.length > 0) {
+            for(let item of root.children) {
+                helper(item, arr, level + 1)
+            }
+        }
+
+    }
+    helper(root, arr, 0)
+    return arr
+};
+// @lc code=end
+
diff --git a/Week 02/id_521/589.n叉树的前序遍历.js b/Week 02/id_521/589.n叉树的前序遍历.js
@@ -0,0 +1,34 @@
+/*
+ * @lc app=leetcode.cn id=589 lang=javascript
+ *
+ * [589] N叉树的前序遍历
+ */
+
+// @lc code=start
+/**
+ * // Definition for a Node.
+ * function Node(val,children) {
+ *    this.val = val;
+ *    this.children = children;
+ * };
+ */
+/**
+ * @param {Node} root
+ * @return {number[]}
+ */
+var preorder = function(root) {
+  let arr = [];
+  function helper(root, arr, k) {
+    if (root !== null) {
+      arr.push(root.val);
+      if (root.children && root.children.length > 0) {
+        for (let item of root.children) {
+          helper(item, arr);
+        }
+      }
+    }
+  }
+  helper(root, arr);
+  return arr;
+};
+// @lc code=end
diff --git a/Week 02/id_521/590.n叉树的后序遍历.js b/Week 02/id_521/590.n叉树的后序遍历.js
@@ -0,0 +1,35 @@
+/*
+ * @lc app=leetcode.cn id=590 lang=javascript
+ *
+ * [590] N叉树的后序遍历
+ */
+
+// @lc code=start
+/**
+ * // Definition for a Node.
+ * function Node(val,children) {
+ *    this.val = val;
+ *    this.children = children;
+ * };
+ */
+/**
+ * @param {Node} root
+ * @return {number[]}
+ */
+var postorder = function(root) {
+    let arr = []
+    function helper(root, arr) {
+        if(root !== null) {
+            if(root.children && root.children.length > 0) {
+                for(let item of root.children) {
+                    helper(item, arr)
+                }
+            }
+            arr.push(root.val)
+        }
+    }
+    helper(root, arr)
+    return arr
+};
+// @lc code=end
+
diff --git a/Week 02/id_521/94.二叉树的中序遍历.js b/Week 02/id_521/94.二叉树的中序遍历.js
@@ -0,0 +1,36 @@
+/*
+ * @lc app=leetcode.cn id=94 lang=javascript
+ *
+ * [94] 二叉树的中序遍历
+ */
+
+// @lc code=start
+/**
+ * Definition for a binary tree node.
+ * function TreeNode(val) {
+ *     this.val = val;
+ *     this.left = this.right = null;
+ * }
+ */
+/**
+ * @param {TreeNode} root
+ * @return {number[]}
+ */
+var inorderTraversal = function(root) {
+    let arr = [];
+    function helper(root) {
+        if(root !== null) {
+            if(root.left !== null) {
+                helper(root.left, arr)
+            }
+            arr.push(root.val)
+            if(root.right !== null) {
+                helper(root.right, arr)
+            }
+        }
+    }
+    helper(root)
+    return arr
+};
+// @lc code=end
+
diff --git a/Week 02/id_521/98.验证二叉搜索树.js b/Week 02/id_521/98.验证二叉搜索树.js
@@ -0,0 +1,77 @@
+/*
+ * @lc app=leetcode.cn id=98 lang=javascript
+ *
+ * [98] 验证二叉搜索树
+ */
+
+// @lc code=start
+/**
+ * Definition for a binary tree node.
+ * function TreeNode(val) {
+ *     this.val = val;
+ *     this.left = this.right = null;
+ * }
+ */
+/**
+ * @param {TreeNode} root
+ * @return {boolean}
+ */
+var isValidBST = function(root) {
+    function helper(root, lower, upper) {
+        //stop 
+        if(root === null) return true
+ 
+        //loginc
+        let val = root.val
+        if(lower !== null && val <= lower) return false
+        if(upper !== null && val >= upper) return false
+        
+        //drill down
+        // 左子节点上界为直接父节点， 下界为往上找，找到第一节点是另一节点的右节点，这个另一个节点就是下界。
+        /**
+         *              10
+         *                \
+         *                 15
+         *                /
+         *               12
+         *              /
+         *             11
+         *   11的上界为12， 下界为10，因为15及其之后的节点都要比10大，即(10< ? < X) 找的轨迹就是
+         *    
+         *               \
+         *               /
+         *              /
+         *             /
+         *
+         */
+        if(!helper(root.left, lower , val)) return false 
+        
+        if(!helper(root.right, val, upper)) return false
+        // 右子节点上界为直接父节点， 上界为找到的第一个节点是另一个节点的左子节点， 这个另一个节点就是上界
+        /**
+         *                  15
+         *                  / 
+         *                 12
+         *                   \
+         *                    13
+         *                     \ 
+         *                      14
+         * 14的下界为13， 上界为15， 因为15的左边节点都要小于它， ( X<?<15 ), 找的轨迹就是
+         *   
+         * 
+         *                    /
+         *                    \
+         *                     \
+         *                      \
+         *     
+         */
+
+         return true
+        
+    }
+    
+    return helper(root, null, null)
+
+};
+// @lc code=end
+
