Follow up for problem “Populating Next Right Pointers in Each Node”. What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example, Given the following binary tree, 1 / \ 2 3 / \ \ 4 5 7 After calling your function, the tree should look like: 1 -> NULL / \ 2 -> 3 -> NULL / \ \ 4-> 5 -> 7 -> NULL Solution: /** * Definition for binary tree with next pointer.
Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note: You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array. Solution: public class Solution { public boolean search(int[] nums, int target) { int lo=0, hi=nums.length-1; while(lo<=hi){ int mid = (lo+hi)/2; if(nums[mid]==target) return true; if(nums[mid]>nums[hi]){ if(nums[mid]>target && nums[lo]<=target) hi=mid; else lo=mid+1; } else if(nums[mid]<nums[hi]){ if(nums[hi]>=target &&
Follow up for “Find Minimum in Rotated Sorted Array”: What if duplicates are allowed? Would this affect the run-time complexity? How and why? Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element. The array may contain duplicates. Solution: public class Solution { public int findMin(int[]
Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Solution: public class Solution { public int search(int[] nums, int target) {
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. Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }
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. Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int
Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int
Given an array where elements are sorted in ascending order, convert it to a height balanced BST. Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] nums) { return sortedArrayToBST(nums, 0, nums.length-1); } public TreeNode sortedArrayToBST(int[] nums, int
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right;