Han Zhu's Study Notes

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. For 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. Thought process: Traverse all root-to-leaf paths. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean hasPathSum ( TreeNode root , int sum ) { if ( root == null ) { return false ; } if ( root . left == null && root . right == null...

Given a binary tree, find the leftmost value in the last row of the tree. Example 1: Input: 2 / \ 1 3 Output: 1 Example 2:  Input: 1 / \ 2 3 / / \ 4 5 6 / 7 Output: 7 Note:  You may assume the tree (i.e., the given root node) is not  NULL . Thought process: BFS. Level order traversal. Use a variable to keep track of the first node of each level. Solution 1 (BFS): 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 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int findBottomLeftValue(TreeNode root) { Queue < TreeNode > queue = new LinkedList <> (); queue.offer(root); TreeNode bl = null; while ( ! queue.isEmpty()) {...

Given an encoded string, return it's decoded string. The encoding rule is:  k[encoded_string] , where the  encoded_string  inside the square brackets is being repeated exactly  k  times. Note that  k  is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,  k . For example, there won't be input like  3a  or  2[4] . Examples: s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s = "2[abc]3[cd]ef", return "abcabccdcdcdef". Thought process: Recursively decode strings inside brackets and append them to result. Solution 1 (Recursive): 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 class Solution { p...

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 Note: Bonus points if you could solve it both recursively and iteratively. Thought process: Recursive: traverse the tree and check if left matches right. Iterative: BFS. Solution 1 (Recursive): 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 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric ( TreeNode root ) { if ( root == null ) { return true ; } return isSymmetric ( root . left , r...

Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. Thought process: Similar to  105. Construct Binary Tree from Preorder and Inorder Traversal . Iterate from end to beginning of the post-order traversal. Attach right sub-tree to root before left. 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 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree ( int [] inorder , int [] postorder ) { Map < Integer , Integer > map = new HashMap <>(); for ( int i = 0 ; i < inorder . length ; i ++) { map . put ( inorder [ i ], i ); } return buildTree ( map , postorder , pos...

Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. Thought process: Iterate through the preorder array. Find the element in the inorder array. The elements to the left are the left subtree and the elements to the right are the right subtree. Recurse down to next level. The base case happens when preorder's index >= preorder.length or when left > right end of inorder array. 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 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree ( int [] preorder , int [] inorder ) { Map < Integer , Integer > map = new HashMap <>(); for ( int i = 0 ; i < inorder...

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"] Thought process: DFS. 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 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List < String > binaryTreePaths ( TreeNode root ) { List < String > paths = new ArrayList <>(); if ( root == null ) { return paths ; } String path = Integer . toString ( root . val ); binaryTreePaths ( root , path , paths ); return paths ; } private void binaryTreePaths ( TreeNode node , String path , List < ...

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols  +  and  - . For each integer, you should choose one from  +  and  -  as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Example 1: Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Note: The length of the given array is positive and will not exceed 20. The sum of elements in the given array will not exceed 1000. Your output answer is guaranteed to be fitted in a 32-bit integer. Thought process: DFS exhaust all possible combinations. Solution 1 (recursion): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public class Solution { public int findTargetSumWays ( int [] nums , int S ) { return ...