Leetcode

题目： In English, we have a concept called root, which can be followed by some other word to form another longer word - let’s call this word successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another". Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length. ...

题目： Implement a MapSum class with insert, and sum methods. For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one. For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix. ...

题目： 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 preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree: 3 / \ 9 20 / \ 15 7 实现： 递归方式，根据二叉树中序遍历和前续遍历，创建二叉树。中序遍历： 左-根-右，前续遍历： 根-左-右， 所以可以通过前续遍历的第一个节点找到根节点，并生成根节点， 因为二叉树没有重复节点， 就 可以在中序遍历数据中找到根节点，再分成左右两个子树，递归执行下去，遍历完所有节点。 通过preorder获取根节点， 通过inorder生成左右子树，查找节点在中序遍历数据组里位置，java可以通过HashMap实现。 不使用map情况下 时间复杂度 O(N^2) , 使用map查找O(N) /** 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 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, 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 2 / \ / \ 3 4 4 3 But the following [1,2,2,null,3,null,3] is not: 1 / \ 2 2 \ \ 3 3 Follow up: Solve it both recursively and iteratively. 实现： 递归方式， 判断左子树的左节点和右子树右节点值是否相等， 判断左子树的右节点和右子树左节点值是否相等 空间复杂度O(N) 时间复杂度 O(N) class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return helper(root.left, root.right); } public boolean helper(TreeNode l, TreeNode r){ if (l == null && r == null){ return true; } else if (l == null || r == null){ return false; } return (l.val == r.val) && helper(l.right, r.left) && helper(l.left, r.right); } } 迭代方式，按照左子树右节点，左节点，右子树的左节点， 右节点，就是每层要比较的顺序， 分别放入各自队列， 再同时弹出队列， 由于不是满二叉树， 每层有空的情况， 所以如果出队列节点全为空，需要继续。 空间复杂度O(N) 时间复杂度 O(N) class Solution { public boolean isSymmetric(TreeNode root) { if (root == null){ return true; } Queue<TreeNode> ql = new LinkedList<>(); Queue<TreeNode> qr = new LinkedList<>(); ql.offer(root.left); qr.offer(root.right); while (!ql.isEmpty() && !qr.isEmpty()){ TreeNode lnode = ql.poll(); TreeNode rnode = qr.poll(); if (lnode == null && rnode == null){ continue; } else if (lnode == null || rnode == null){ return false; } else if (lnode.val != rnode.val){ return false; } ql.offer(lnode.left); ql.offer(lnode.right); qr.offer(rnode.right); qr.offer(rnode.left); } return true; } }

题目： 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], 3 / \ 9 20 / \ 15 7 return its depth = 3. 解题： 深度优先搜索方式，分别找到左右子树最大的深度+1即可；广度优先搜索，逐层遍历找到最大层数返回。 实现 DFS， 空间复杂度O(N) 时间复杂度 O(N) /** * 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: int maxDepth(TreeNode* root) { if (!root) {return 0;} return 1 + max( maxDepth(root->left), maxDepth(root->right)); } }; 实现： BFS 空间复杂度O(N) 时间复杂度 O(N) /** * 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: int maxDepth(TreeNode* root) { if (!root) {return 0;} return 1 + max( maxDepth(root->left), maxDepth(root->right)); } };*/ class Solution { public: int maxDepth(TreeNode* root) { if (!root){ return 0; } queue<TreeNode*> q; int depth=0; q.push(root); while(!q.empty()){ depth ++; int level_size = q.size(); for (int i=0; i<level_size; i++){ TreeNode *node = q.front(); q.pop(); if (node->left){ q.push(node->left); } if (node->right){ q.push(node->right); } } } return depth; } };

题目： 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], 3 / \ 9 20 / \ 15 7 return its minimum depth = 2. 解题： 深度优先搜索方式，分别找到左右子树最小+1；广度优先搜索，逐层遍历找到叶子节点返回层数。 实现： DFS 空间复杂度O(N) 时间复杂度 O(N) class Solution { public: int minDepth(TreeNode* root) { if(!root) return 0; if(!root->left) return 1+minDepth(root->right); if(!root->right) return 1+minDepth(root->left); return 1+min(minDepth(root->left), minDepth(root->right)); } }; 实现： BFS 空间复杂度O(N) 时间复杂度 O(N) /** * 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: int minDepth(TreeNode* root) { if (!root){ return 0; } int depth = 0; queue<TreeNode *> q; q.push(root); while(!q.empty()){ depth++; int level_size = q.size(); for(int i=0; i<level_size; i++){ TreeNode *node = q.front(); q.pop(); if (!node->left&&!node->right){ return depth; } if (node->left){ q.push(node->left); } if (node->right){ q.push(node->right); } } } return depth; } };

题目： 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], 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] 解题： 两种方式处理， 广度优先搜索借助队列，一层一层处理，并放入二维数组； 深度优先搜索借助栈， 一个一个处理， 将每一个元素方式所属层对应的一维数组中。 实现： BFS 使用队列实现 /** * 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: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (!root) { return result; } queue<TreeNode*> q; q.push(root); while (!q.empty()){ vector<int> current; int level_size = q.size(); for (int i=0; i<level_size; i++){ TreeNode* node = q.front(); q.pop(); current.push_back(node->val); if (node->left) { q.push(node->left); } if (node->right) { q.push(node->right); } } result.push_back(current); } return result; } }; 实现： DFS 递归实现： class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (!root){ return result; } result = _dfs(root, 0, result); return result; } vector<vector<int>> _dfs(TreeNode *node, int level, vector<vector<int>> &res){ if (!node){ return res; } if (res.size() < level+1){ res.push_back({}); } res[level].push_back(node->val); _dfs(node->left, level+1, res); _dfs(node->right, level+1, res); return res; } };

题目： Given a binary tree, return the postorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [3,2,1] Follow up: Recursive solution is trivial, could you do it iteratively? 解题： 遍历顺序“根-左-右” 实现： 使用栈实现 从根节点开始，先将根节点压入栈，保存结果值，然后移动到右节点， 保证“根-右边”顺序， 为空后出栈，取其左节点入栈中。这样入栈就保证了访问顺序为“根-右-左”， 出栈实现“左-右-根”。 class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> ss; TreeNode *p= root, *t; while(!ss.empty()||p){ if (p){ ss.push(p); res.insert(res.begin(), p->val); p = p->right; } else { p=ss.top(); ss.pop(); p= p->left; } } return res; } }; 实现： 递归实现 class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector <int> res; postorder(root, res); return res; } void postorder(TreeNode *root, vector<int> &res){ if (!root) { return; } if (root->left) { postorder(root->left, res); } if (root->right){ postorder(root->right, res); } res.push_back(root->val); } }; 参考: [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历