刷题记录

Problem: Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order. Examples 1 Input: 5 / \ 2 -3 return [2, -3, 4], since all the values happen only once, return all of them in any order. Examples 2 Input: 5 / \ 2 -5 return [2], since 2 happens twice, however -5 only occur once. Note:  You may assume the sum of values in any subtree is in the range of 32-bit signed integer. Analysis: Very straight forward divide and conquer. Use a map to record the frequency of sum. Mean while, use keep updating the most occurrence.  Solution: 1: class Solution { 2: int max = 0; 3: public int[] findFrequentTreeSum(TreeNode root) { 4: Map<Integ...

Problem: Given a Binary Search Tree (BST) with root node  root , and a target value  V , split the tree into two subtrees where one subtree has nodes that are all smaller or equal to the target value, while the other subtree has all nodes that are greater than the target value.  It's not necessarily the case that the tree contains a node with value  V . Additionally, most of the structure of the original tree should remain.  Formally, for any child C with parent P in the original tree, if they are both in the same subtree after the split, then node C should still have the parent P. You should output the root TreeNode of both subtrees after splitting, in any order. Example 1: Input: root = [4,2,6,1,3,5,7], V = 2 Output: [[2,1],[4,3,6,null,null,5,7]] Explanation: Note that root, output[0], and output[1] are TreeNode objects, not arrays. The given tree [4,2,6,1,3,5,7] is represented by the following diagram: 4 / \ ...

Problem: Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages: Search for a node to remove. If the node is found, delete the node. Note:  Time complexity should be O(height of tree). Example: root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / \ 4 6 / \ 2 7 Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7 Analysis: When we found the target node, we need to use the smallest node on its right branch to replace it. Then we need to call deleteNode again to delete the smallest node. Solution: class Solution { public TreeNode deleteNode(TreeNode root, int key) { ...

Problem: Given a binary tree rooted at  root , the  depth  of each node is the shortest distance to the root. A node is  deepest  if it has the largest depth possible among any node in the  entire tree . The subtree of a node is that node, plus the set of all descendants of that node. Return the node with the largest depth such that it contains all the deepest nodes in its subtree. Example 1: Input: [3,5,1,6,2,0,8,null,null,7,4] Output: [2,7,4] Explanation: We return the node with value 2, colored in yellow in the diagram. The nodes colored in blue are the deepest nodes of the tree. The input "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" is a serialization of the given tree. The output "[2, 7, 4]" is a serialization of the subtree rooted at the node with value 2. Both the input and output have TreeNode type. Analysis: Very similar to LCA. Use post order divide and conquer approach. Depth is the standard to decide return. Use a result ob...

Problem: Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are  + ,  -  and  * . Example 1: Input: "2-1-1" Output: [0, 2] Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2 Example 2: Input: "2*3-4*5" Output: [-34, -14, -10, -10, 10] Explanation: (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10 Analysis: Divide and conquer. The total result is the Cartesian set of sub results. If we divide a "+" operator, get left result [10,20,30] right result [3,6,8]. Then we will have 3*3 = 9 different results. Solution: The current input is number is when there is no divide, the temp result size is zero. class Solution { Map< String , List< Integer > > map = new HashMap<> (); public List< Integer > diffWaysToCompute ( String input) { if (...

Problem: Given a binary search tree and the lowest and highest boundaries as  L  and  R , trim the tree so that all its elements lies in  [L, R]  (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree. Example 1: Input: 1 / \ 0 2 L = 1 R = 2 Output: 1 \ 2 Example 2: Input: 3 / \ 0 4 \ 2 / 1 L = 1 R = 3 Output: 3 / 2 / 1 Analysis: If current root's val < L, we skip it and try to search its right child. If current root.val > R, we skip it and try to search its left child. Solution: class Solution { public TreeNode trimBST ( TreeNode root, int L , int R ) { if (root == null) return null; TreeNode left = trimBST(root . left, L , R ); TreeNode right = trimBST(root . right, L , R ); if (root . val < L ) return right; ...

思路： 有多种解法，最有价值的就是用heap和分治法。 解法一： heap 把所有listnode放到heap里面。然后挨个从heap里面取，这样可以保证每次取的都是最小值。连到result list上。如果heap.poll().next != null，把heap.poll().next放进heap里面。 代码如下： /** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /** * @param lists: a list of ListNode * @return: The head of one sorted list. */ public ListNode mergeKLists(List<ListNode> lists) { // write your code here if(lists.size() == 0 || lists == null ) { return null; } Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>() { public int compare(ListNode a, ListNode b) { return a.val - b.val; } }); // initialize heap for(ListNode n: lists) { if(n !...

Problem: Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys  less than  the node's key. The right subtree of a node contains only nodes with keys  greater than  the node's key. Both the left and right subtrees must also be binary search trees. Example 1: Input: 2 / \ 1 3 Output: true Example 2: 5 / \ 1 4   / \   3 6 Output: false Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value   is 5 but its right child's value is 4. Analysis: 5/30/2018 Update: The iterative inorder traversal approach is trivial. What is worth to know is the recursive divide and conquer approach. Details see code. Solution: class Solution { public boolean isValidBST ( TreeNode root) { return helper(root, Long . MIN_VALUE, Long . MAX_VALUE); } priva...

Problem: Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the depth of the two subtrees of  every  node never differ by more than 1. Example 1: Given the following tree  [3,9,20,null,null,15,7] : 3 / \ 9 20 / \ 15 7 Return true. Example 2: Given the following tree  [1,2,2,3,3,null,null,4,4] : 1 / \ 2 2 / \ 3 3 / \ 4 4 Return false. 12/29/2017 update Solution 1: Brute force, /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isBalanced(TreeNode root) { if (root == null) return true; return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.r...

思路： DC和traversal 结合。用全局变量记录临时的min sum和sub tree。

Problem: 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. 4/21/2018 Analysis: 这道题比求mini depth 简单。 Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxDepth ( TreeNode root) { if (root == null) return 0 ; int left = maxDepth(root . left) + 1 ; int right = maxDepth(root . right) + 1 ; return Math . max(left, right); } }