刷题记录

Problem: Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Let's take the following BST as an example, it may help you understand the problem better: We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element. The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list. Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first...

Problem: 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 Analysis: 如果当前对比的node1 和node 2相等，要符合symmetric tree我们需要比较node1.left == node2.right && node1.right == node2.left. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public boolean isSymmetric ( TreeNode root ) { return root == null || helper ( root . left , root . right ); } private boolean helper ( TreeNode left , TreeNode right ) { if ( left == null && right == null) return true; if (( left != null && right == null) || ( left == null && right != null) || left . val != right . val ) return false; r...

Problem: We are given a binary tree (with root node  root ), a  target  node, and an integer value  K . Return a list of the values of all nodes that have a distance  K  from the  target  node.  The answer can be returned in any order. Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4] , target = 5 , K = 2 Output: [7,4,1] Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1. Note that the inputs "root" and "target" are actually TreeNodes. The descriptions of the inputs above are just serializations of these objects. Analysis: 这道题和之前那道 742. Closest Leaf in a Binary Tree  类似。都是先建图然后BFS。不同点在于，这道题如果按742的图的构建方式，test case [1] 通过不了， 因为node 1根本不会出现在图中。就会出现null pointer错误。 另外一个点就是，在while循环一开始判断k的值，循环底部k--。如果反过来而且k==0, 就得不到结果。 Solution: 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 ...

Problem: Given a binary tree with  n  nodes, your task is to check if it's possible to partition the tree to two trees which have the equal sum of values after removing  exactly  one edge on the original tree. Example 1: Input: 5 / \ 10 10 / \ 2 3 Output: True Explanation: 5 / 10 Sum: 15 10 / \ 2 3 Sum: 15 Example 2: Input: 1 / \ 2 10 / \ 2 20 Output: False Explanation: You can't split the tree into two trees with equal sum after removing exactly one edge on the tree. Note: The range of tree node value is in the range of [-100000, 100000]. 1 <= n <= 10000 Analysis: Get all sums, check whether the collections of sums contains totalSum/2. Do not include total sum to set of sums, if the total sum is 0, it will qualify.  Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public boolean checkEqualTree(TreeNode ro...

Problem: Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. Example: Input: The root of a Binary Search Tree like this: 5 / \ 2 13 Output: The root of a Greater Tree like this: 18 / \ 20 13 Analysis: Reverse traversal from right to root to left. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { int sum = 0; public TreeNode convertBST(TreeNode root) { if (root == null ) return null ; convertBST(root.right); int val = root.val; root.val += sum; sum += val; convertBST(root.left); return root; } }

Problem: You need to construct a binary tree from a string consisting of parenthesis and integers. The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure. You always start to construct the  left  child node of the parent first if it exists. Example: Input: "4(2(3)(1))(6(5))" Output: return the tree root node representing the following tree: 4 / \ 2 6 / \ / 3 1 5 Note: There will only be  '(' ,  ')' ,  '-'  and  '0'  ~  '9'  in the input string. An empty tree is represented by  ""  instead of  "()" . Analysis: Partition string to get the correct string for subtree. The above example can be partition to root: 4, left: 2(3)(1), right 6(5).  Solution: class Solution { p...

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: Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a  binary search tree . There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure. The encoded string should be as compact as possible. Analysis: This problem needs to encode as compact as possible so that "null" should be avoided. We use recursive preorder. While desalinizing, use lower bound and uppder bound to decide the legitimacy of current value. Converting data to queue, to reduce remove complexity to constant.  Similar problem 98. Validate Binary Search Tree W...

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 binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a  full binary tree , but some nodes are null. The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the  null  nodes between the end-nodes are also counted into the length calculation. Example 1: Input: 1 / \ 3 2 / \ \ 5 3 9 Output: 4 Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9). Example 2: Input: 1 / 3 / \ 5 3 Output: 2 Explanation: The maximum width existing in the third level with the length 2 (5,3). Example 3: Input: 1 / \ 3 2 / 5 Output: 2 Explanation:...

Problem: Given a binary tree  where every node has a unique value , and a target key  k , find the value of the nearest leaf node to target  k  in the tree. Here,  nearest  to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a  leaf  if it has no children. In the following examples, the input tree is represented in flattened form row by row. The actual  root  tree given will be a TreeNode object. Example 1: Input: root = [1, 3, 2], k = 1 Diagram of binary tree: 1 / \ 3 2 Output: 2 (or 3) Explanation: Either 2 or 3 is the nearest leaf node to the target of 1. Example 2: Input: root = [1], k = 1 Output: 1 Explanation: The nearest leaf node is the root node itself. Example 3: Input: root = [1,2,3,4,null,null,null,5,null,6], k = 2 Diagram of binary tree: 1 / \ 2 3 /...

Problem: 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. For example: Given binary tree, 5 / \ 1 5 / \ \ 5 5 5 return  4 . Analysis: 6/8/2018  Helper returns whether the root is uni-value subtree and root's val equals to its parent's value. If both left and right return true, we know that left and right are uni-value subtree and their values equal to root.val. So there will be one more univalue subtree, the root plus its children. -------------------------------------------------------------------------------------------------------------------------------------------- Think about what exactly makes a uni-value subtree. 1. left subtree is uni-value subtree 2. right subtree is uni-value subtree 3. left != null && right != null && left.val == right.val == root.val Solution: class...

Problem: You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree. Example 1: Input: Binary tree: [1,2,3,4] 1 / \ 2 3 / 4 Output: "1(2(4))(3)" Explanation: Originallay it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)". Example 2: Input: Binary tree: [1,2,3,null,4] 1 / \ 2 3 \ 4 Output: "1(2()(4))(3)" Explanation: Almost the same as the first example, except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the outpu...