刷题记录

Problem: Given a binary tree, return the values of its boundary in  anti-clockwise  direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes. Left boundary  is defined as the path from root to the  left-most  node.  Right boundary  is defined as the path from root to the  right-most  node. If the root doesn't have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees. The  left-most  node is defined as a  leaf  node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node. The  right-most  node is also defined by the same way with left and right exchanged. Example 1 Input: 1 \ 2 / \ 3 4 Ouput: [1, 3, ...

Problem: You need to find the largest value in each row of a binary tree. Example: Input: 1 / \ 3 2 / \ \ 5 3 9 Output: [1, 3, 9] Analysis: 这道题是无脑用BFS。居然有人装逼用DFS,不知道怎么想的。 Solution: class Solution { public List< Integer > largestValues ( TreeNode root) { List< Integer > res = new ArrayList<> (); if (root == null) return res; Queue< TreeNode > queue = new LinkedList<> (); queue . offer(root); while ( ! queue . isEmpty()) { int size = queue . size(); int max = Integer . MIN_VALUE; for ( int i = 0 ; i < size; i ++ ) { TreeNode cur = queue . poll(); max = Math . max(max, cur . val); if (cur . left != null) queue . offer(cur . left); if (cur . right != null) queue . offer(...

Problem: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree. Example 1: Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: Merged tree: 3 / \ 4 5 / \ \ 5 4 7 7/22/2018 update: A better solution: class Solution { public TreeNode mergeTrees ( TreeNode t1 , TreeNode t2 ) { if ( t1...

Problem: Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the  longest path between any two nodes in a tree. This path may or may not pass through the root. Example: Given a binary tree  1 / \ 2 3 / \ 4 5 Return  3 , which is the length of the path [4,2,1,3] or [5,2,1,3]. Analysis: The possible diameter is the node's left max depth + node's right max depth. Solution: class Solution { int max; public int diameterOfBinaryTree ( TreeNode root) { if (root == null) return 0 ; max = Integer . MIN_VALUE; depth(root); return max; } private int depth ( TreeNode root) { if (root == null) return 0 ; int left = depth(root . left); int right = depth(root . right); max = Math . max(left + right, max); return Math . max(left...

Problem: Given a binary tree, return the  bottom-up level order  traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree  [3,9,20,null,null,15,7] , 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ] Analysis: We can do normal level order and reverse the result. Another approach is DFS, create new List<Int> on the go. Solution: BFS: class Solution { public List< List< Integer > > levelOrderBottom ( TreeNode root) { List< List< Integer > > res = new ArrayList<> (); if (root == null) return res; Queue< TreeNode > queue = new LinkedList<> (); Stack< List< Integer > > stack = new Stack<> (); queue . offer(root); while ( ! queue . isEmpty()) { int size = queue . size(); ...

Problem: Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree: 1 / \ 2 3 \ 5 All root-to-leaf paths are: ["1->2->5", "1->3"] Analysis: Typical DFS, but to remember the ending condition is root.left == null and root.right == null. Solution: After some optimization of code structure; class Solution { public List< String > binaryTreePaths ( TreeNode root) { List< String > res = new ArrayList<> (); if (root == null) return res; dfs(root, new StringBuilder (), res); return res; } private void dfs ( TreeNode root, StringBuilder sb, List< String > res) { if (root == null) return ; int len = sb . length(); sb . append( Integer . toString(root . val)); if (root . left == null && root . right == null) { res . add(sb . toString()); } else...

Problem: Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: The root is the maximum number in the array. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number. Construct the maximum tree by the given array and output the root node of this tree. Example 1: Input: [3,2,1,6,0,5] Output: return the tree root node representing the following tree: 6 / \ 3 5 \ / 2 0 \ 1 7/9/2018 update: Finally went through the stack solution. Maintain a increasing stack from top to bottom. If current node's val is greater than stack top, then pop stack add poped node to current's left. By doing so, we add previous smaller nodes to current's left. If stack is not empty after the above process. stack pop node's value...

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; ...

Problem: Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,null,2]   1   /  3   \   2 Output: [3,1,null,null,2]   3   /  1   \   2 Example 2: Input: [3,1,4,null,null,2] 3 / \ 1 4   /   2 Output: [2,1,4,null,null,3] 2 / \ 1 4   /  3 Analysis: From the example above we know that the first element is greater than its successor, the second element is smaller than its predecessor. We can find first and second swapped node easily with inorder traversal. Solution: class Solution { public void recoverTree ( TreeNode root) { if (root == null) return ; TreeNode prev = null; TreeNode first = null; TreeNode second = null; Stack< TreeNode > stack = new Stack<> (); TreeNode cur = root; while ( ! stack . isEmp...

Problem: Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target. Note: Given target value is a floating point. You are guaranteed to have only one unique value in the BST that is closest to the target. 8/19/2018 update: 如果root.val > target, 说明了root的右边肯定离target更远，所以要往左走。 -------------- -------------- -------------- -------------- -------------- -------------- -------------- -------------- -------------- -------------- Analysis: The result is updated by the smaller different between current node's val and target.  Solution: class Solution { public int closestValue ( TreeNode root, double target) { int res = root . val; while (root != null) { if ( Math . abs(root . val - target) < Math . abs(res - target)) { res = root . val; } root = root . val > target ? root . left : root . right; } return ...

Problem: Given a binary tree, return the  vertical order  traversal of its nodes' values. (ie, from top to bottom, column by column). If two nodes are in the same row and column, the order should be from  left to right . Examples: Given binary tree  [3,9,20,null,null,15,7] , 3 /\ / \ 9 20 /\ / \ 15 7 return its vertical order traversal as: [ [9], [3,15], [20], [7] ] Given binary tree  [3,9,8,4,0,1,7] , 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 return its vertical order traversal as: [ [4], [9], [3,0,1], [8], [7] ] Given binary tree  [3,9,8,4,0,1,7,null,null,null,2,5]  (0's right child is 2 and 1's left child is 5), 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2 return its vertical order traversal as: [ [4], [9,5], [3,0,1], [8,2], [7] ] 7/5/2018 update: To further optimize the solution. Use another queue to keep trac...

Problem: Given a binary tree containing digits from  0-9  only, each root-to-leaf path could represent a number. An example is the root-to-leaf path  1->2->3  which represents the number  123 . Find the total sum of all root-to-leaf numbers. Note:  A leaf is a node with no children. Example: Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12 . The root-to-leaf path 1->3 represents the number 13 . Therefore, sum = 12 + 13 = 25 . Example 2: Input: [4,9,0,5,1] 4 / \ 9 0  / \ 5 1 Output: 1026 Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026 . 7/5/2018 update 第二遍也是想的brute force。但面试的时候有可能在面试官提示下做出高级方法。。。 ---------------------------- ---------------------------- ...

Problem: Given a list of words, we may encode it by writing a reference string  S  and a list of indexes  A . For example, if the list of words is  ["time", "me", "bell"] , we can write it as  S = "time#bell#"  and  indexes = [0, 2, 5] . Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character. What is the length of the shortest reference string S possible that encodes the given words? Example: Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes = [0, 2, 5 ]. Analysis: 核心思想是合并suffix一样的单词。比如time和me，suffix是一个的，可以把me去掉。可以用2种方法做。 Approach 1: Hash set 先把所有的word加入到一个set里面。然后遍历所有word。 对于每一个word，从index 1开始拆分suffix, 看这个word的suffix在不在set里面。如果在则从set里面删除。 class Solution { public int minimumLengthEncoding ( String [] words) { Set< String > set = new HashS...