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 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 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. 解题： 深度优先搜索方式，分别找到左右子树最大的深度+1即可；广度优先搜索，逐层遍历找到最大层数返回。 ...

题目： 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] ] 解题： 两种方式处理， 广度优先搜索借助队列，一层一层处理，并放入二维数组； 深度优先搜索借助栈， 一个一个处理， 将每一个元素方式所属层对应的一维数组中。 ...

题目： 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? 解题： 遍历顺序“根-左-右” 实现： 使用栈实现 从根节点开始，先将根节点压入栈，保存结果值，然后移动到右节点， 保证“根-右边”顺序， 为空后出栈，取其左节点入栈中。这样入栈就保证了访问顺序为“根-右-左”， 出栈实现“左-右-根”。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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; } }; 实现： 递归实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 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 二叉树的后序遍历