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 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. Thought process: Record root.val and recursively search for the closest value: If root.val < target, search in the right sub-tree. If abs(result - target) < abs(root.val - target), return result. If root.val >= target, search in the left sub-tree. If abs(result - target) < abs(root.val - target), return result. 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 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int closestValue ( TreeNode root , double target ) { int closest =...

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 Thought process: Recursively search for the node to be deleted. There are several cases: Node.left == null && node.right == null: return null. Node.left == null: return node.right. Node.right == null: return node.left. Otherwise, get the minimum of the node's right sub-tr...

Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse). For example, 1 \ 3 / \ 2 4 \ 5 Longest consecutive sequence path is  3-4-5 , so return  3 . 2 \ 3 / 2 / 1 Longest consecutive sequence path is  2-3 ,not 3-2-1 , so return  2 . Thought process: Recursion. Use an instance variable to keep track of longest path. Base case: Node == null: update longest and return. Node.val != parent.val + 1: update longest and reset current path length. 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; * TreeN...

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 search tree, write a function  kthSmallest  to find the  k th smallest element in it. Note:  You may assume k is always valid, 1 ≤ k ≤ BST's total elements. Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine? Thought process: Use instance variables to keep track of k and result. Do an in-order traversal of the BST. As I traverse it in ascending order, decrement k for each node. Solution 1 (In-order traversal): 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 { private int number ; private int count ; public int kthSmallest ( TreeNode root , in...

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target. Example 1: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True Example 2: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False Thought process: In-order traversal. 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 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean findTarget ( TreeNode root , int k ) { List < Integer > nodes = new ArrayList <>(); inOrder ( root , nodes ); int i = 0 ; int j = nodes . size () - 1 ; while ( i < j ) { ...