Algorithm

题目： Implement a trie with insert, search, and startsWith methods. Example: 1 2 3 4 5 6 7 8 Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true Note: You may assume that all inputs are consist of lowercase letters a-z. All inputs are guaranteed to be non-empty strings. 实现： TrieTree是一个多叉树，是解决字符串快速匹配问题的数据结构， 他用于存储一个字符串，每个TrieTree的节点代表一个字符串/字符串前缀，每个节点可以有多个孩子节点，指向不同子节点不同路径代表不同的字符串，子节点的字符串是由本子节点的字符加上从根节点到本节点路径上的字符组成。 本地实现上， 节点的子节点使用数组或哈希表存储，只处理26个字母，通过判断子节点指针是否为空判断该字符是否存在。 具体实现参考leetcode提供的伪代码 ...

题目： Given a binary tree, count the number of uni-value subtrees. A Uni-value subtree means all nodes of the subtree have the same value. Example : 1 2 3 4 5 6 7 8 9 Input: root = [5,1,5,5,5,null,5] 5 / \ 1 5 / \ \ 5 5 5 Output: 4 实现： 创建判断相同值子树方法isUnivalSubtrees， 判断其左、右节点与父节点是否相同，判定为Uni-value subtree（比较子节点与父节点val值时要先判断下对应left， right是否为空）， 分别判断左子树和右子树的是否为Uni-value subtree， 如果是计数器累加。 isUnivalSubtrees 时间 复杂度O(n) 嵌入 countUnivalSubtrees后 O(n^2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: the given tree * @return: the number of uni-value subtrees. */ int countUnivalSubtrees(TreeNode * root) { int total = 0; if (root == nullptr){ return 0; } total = countUnivalSubtrees(root->left) + countUnivalSubtrees(root->right); if (isUnivalSubtrees(root)){ total +=1; } return total; } private: bool isUnivalSubtrees(TreeNode * root){ if (root == nullptr) { return true; } if (root->left!=nullptr && root->left->val != root->val) { return false; } if (root->right!=nullptr && root->right->val != root->val){ return false; } if (isUnivalSubtrees(root->left) && isUnivalSubtrees(root->right)){ return true; } return false; } }; 实现： 判断是否为Uni-value subtree的同时累计符合条件的子树数量，一起返回。 O(N) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: the given tree * @return: the number of uni-value subtrees. */ int countUnivalSubtrees(TreeNode * root) { bool isUnival = true; return helperCount(root, isUnival); } int helperCount(TreeNode *root, bool& isUnival) { if (root == nullptr) { isUnival = true; return 0; } bool isLeftunival = true; bool isRightunival = true; int leftCount = 0; int rightCount = 0; leftCount = helperCount(root->left, isLeftunival); rightCount = helperCount(root->right, isRightunival); if (!isLeftunival || !isRightunival){ isUnival = false; } if (root->left !=nullptr && root->left->val != root->val ){ isUnival = false; } if (root->right !=nullptr && root->right->val != root->val ){ isUnival = false; } if (isUnival){ return leftCount+rightCount+1; } else { return leftCount+rightCount; } } }; 实现： 使用C++ pair ，判断Uni-value subtree和累计值放到一起返回。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: the given tree * @return: the number of uni-value subtrees. */ int countUnivalSubtrees(TreeNode * root) { pair<int, bool> re = helperCount(root); return re.first; } pair<int,bool> helperCount(TreeNode *root) { pair<int, bool> res = {0, true}; if (root == nullptr) { return res; } pair<int, bool> left, right; left = helperCount(root->left); right = helperCount(root->right); if (!left.second || !right.second){ res.second = false; } if (root->left !=nullptr && root->left->val != root->val ){ res.second = false; } if (root->right !=nullptr && root->right->val != root->val ){ res.second = false; } if (res.second){ res = {left.first+right.first+1, true}; } else { res = {left.first+right.first, false}; } return res; } }; 参考及引用: https://www.youtube.com/watch?v=7HgsS8bRvjo

题目： Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given 1 2 preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree: 1 2 3 4 5 3 / \ 9 20 / \ 15 7 实现： 递归方式，根据二叉树中序遍历和前续遍历，创建二叉树。中序遍历： 左-根-右，前续遍历： 根-左-右， 所以可以通过前续遍历的第一个节点找到根节点，并生成根节点， 因为二叉树没有重复节点， 就 可以在中序遍历数据中找到根节点，再分成左右两个子树，递归执行下去，遍历完所有节点。 通过preorder获取根节点， 通过inorder生成左右子树，查找节点在中序遍历数据组里位置，java可以通过HashMap实现。 不使用map情况下 时间复杂度 O(N^2) , 使用map查找O(N) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 /** java * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { Map<Integer, Integer> treemap = new HashMap <>(); for (int i=0; i<inorder.length; i++){ treemap.put(inorder[i], i); } AtomicInteger rootindex = new AtomicInteger(0); return helper(preorder, inorder, 0, inorder.length -1, rootindex, treemap); } public TreeNode helper(int[] preorder, int[] inoder, int left, int right, AtomicInteger index, Map<Integer, Integer> treemap) { if (left > right){ return null; } //new node, set root int val = preorder[index.intValue()]; TreeNode node = new TreeNode(val); index //search inorder int root = treemap.get(val); //left substree node.left = helper(preorder, inoder, left, root-1, index, treemap); //right substree node.right = helper(preorder, inoder, root+1, right, index, treemap); return node ; } } 参考及引用: techiedelight-construct-binary-tree-from-inorder-preorder-traversal

题目： Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4] ...

题目： Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given 1 2 inorder = [9,3,15,20,7] postorder = [9,15,7,20,3] Return the following binary tree: 1 2 3 4 5 3 / \ 9 20 / \ 15 7 实现： 递归方式，根据二叉树中序遍历和后续遍历，创建二叉树。中序遍历： 左-根-右， 后续遍历： 左-右-根， 所以可以通过后续遍历的最后一个节点找到根节点，并生成根节点， 因为二叉树没有重复节点， 就 可以在中序遍历数据中找到根节点，再分成左右两个子树，递归执行下去，遍历完所有节点。 通过postorder获取根节点， 通过inorder生成左右子树，查找节点在中序遍历数据组里位置，可以通过unordered_map实现。 不使用map情况下 时间复杂度 O(N^2) , 使用map查找O(N) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { unordered_map <int, int> treemap; for (int i=0; i<inorder.size();i++) { treemap[inorder[i]] = i; } int index = inorder.size()-1; return helper(inorder, postorder, 0, inorder.size()-1, &index, treemap); } TreeNode *helper(vector<int> & inorder, vector<int>& postorder, int left, int right, int *index , unordered_map<int, int>&treemap){ //check if (left > right){ return NULL; } // create root node /* destory postorder vector int val = postorder.back(); TreeNode *node = new TreeNode(val); postorder.pop_back(); */ int val = postorder[*index]; TreeNode *node = new TreeNode(val); (*index)--; // search inorder by array /* int root = -1; for (int i=left ; i <=right; i ++){ if (val == inorder[i]){ root = i; break; } } if (root == -1){ return node; }*/ // search inorder by map int root = treemap[val]; // create left & right node node->right = helper(inorder, postorder, root+1, right, index, treemap); node->left = helper(inorder, postorder, left, root-1, index, treemap); return node; } };

题目： Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree and sum = 22, 1 2 3 4 5 6 7 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22. ...

题目： Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 2 3 4 5 1 / \ 2 2 / \ / \ 3 4 4 3 But the following [1,2,2,null,3,null,3] is not: 1 2 3 4 5 1 / \ 2 2 \ \ 3 3 Follow up: Solve it both recursively and iteratively. ...

题目： Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 1 2 3 4 5 3 / \ 9 20 / \ 15 7 return its depth = 3. ...

题目： Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 1 2 3 4 5 3 / \ 9 20 / \ 15 7 return its minimum depth = 2. ...

题目： Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], 1 2 3 4 5 3 / \ 9 20 / \ 15 7 return its level order traversal as: 1 2 3 4 5 [ [3], [9,20], [15,7] ] 解题： 两种方式处理， 广度优先搜索借助队列，一层一层处理，并放入二维数组； 深度优先搜索借助栈， 一个一个处理， 将每一个元素方式所属层对应的一维数组中。 ...