Populating Next Right Pointers in Each Node II (Java and Python)

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 : The main idea actually is tree level traversal, we can just use one node called current represent current level (start from root) and two other nodes which called nextLevelHead and nextLevelEnd to record next level's left child and right child and when current node is null then exchange current and nextLevelHead until nextLevelHead is also null

	/*
	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
	*/
	/**
	* Definition for binary tree with next pointer.
	* public class TreeLinkNode {
	* int val;
	* TreeLinkNode left, right, next;
	* TreeLinkNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public void connect(TreeLinkNode root) {
	if (root==null){
	return;
	}
	TreeLinkNode current=root;
	TreeLinkNode nextLevelHead=null;
	TreeLinkNode nextLevelEnd=null;
	while (current!=null){
	if (current.left!=null){
	if (nextLevelHead==null){
	nextLevelHead=current.left;
	nextLevelEnd=nextLevelHead;
	}
	else{
	nextLevelEnd.next=current.left;
	nextLevelEnd=nextLevelEnd.next;
	}
	}
	if (current.right!=null){
	if (nextLevelHead==null){
	nextLevelHead=current.right;
	nextLevelEnd=nextLevelHead;
	}
	else{
	nextLevelEnd.next=current.right;
	nextLevelEnd=nextLevelEnd.next;
	}
	}
	current=current.next;
	if (current==null){
	current=nextLevelHead;
	nextLevelHead=null;
	nextLevelEnd=null;
	}
	}
	}
	}

view raw PopulatingNextRightPointersInEachNodeII.java hosted with ❤ by GitHub

	"""
	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
	"""
	# Definition for a binary tree node
	# class TreeNode:
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None
	# self.next = None
	class Solution:
	# @param root, a tree node
	# @return nothing
	def connect(self, root):
	if not root:
	return
	current=root
	nextLevelHead=None
	nextLevelEnd=None
	while (current):
	if (current.left):
	if nextLevelHead:
	nextLevelEnd.next=current.left
	nextLevelEnd=nextLevelEnd.next
	else:
	nextLevelHead=current.left
	nextLevelEnd=nextLevelHead
	if (current.right):
	if nextLevelHead:
	nextLevelEnd.next=current.right
	nextLevelEnd=nextLevelEnd.next
	else:
	nextLevelHead=current.right
	nextLevelEnd=nextLevelHead
	current=current.next
	if (not current):
	current=nextLevelHead
	nextLevelHead=None
	nextLevelEnd=None

view raw PopulatingNext RightPointersInEachNodeII.py hosted with ❤ by GitHub

Palindrome Number (Java and Python)

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem

	/*
	Determine whether an integer is a palindrome. Do this without extra space.
	click to show spoilers.
	Some hints:
	Could negative integers be palindromes? (ie, -1)
	If you are thinking of converting the integer to string, note the restriction of using extra space.
	You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
	There is a more generic way of solving this problem.
	*/
	// without consider about overflow
	public boolean isPalindrome(int x) {
	if (x<0){
	return false;
	}
	int current=0;
	int y=x;
	while (y!=0){
	current=current*10+(y%10);
	y=y/10;
	}
	return current==x;
	}
	// considered overflow
	public class Solution {
	public boolean isPalindrome(int x){
	if (x<0){
	return false;
	}
	int divider=1;
	while (x/divider>=10){
	divider*=10;
	}
	while (x!=0){
	int right=x%10;
	int left=x/divider;
	if (right!=left){
	return false;
	}
	x%=divider;
	x/=10;
	divider/=100;
	}
	return true;
	}

view raw PalindromeNumber.java hosted with ❤ by GitHub

	"""
	Determine whether an integer is a palindrome. Do this without extra space.
	click to show spoilers.
	Some hints:
	Could negative integers be palindromes? (ie, -1)
	If you are thinking of converting the integer to string, note the restriction of using extra space.
	You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
	There is a more generic way of solving this problem.
	"""
	class Solution:
	# @return a boolean
	def isPalindrome(self, x):
	if x<0:
	return False
	divider=1
	while(x/divider>=10):
	divider*=10
	while(x!=0):
	left=x/divider
	right=x%10
	if left!=right:
	return False
	x%=divider
	x/=10
	divider/=100
	return True

view raw PalindromeNumber.py hosted with ❤ by GitHub

Sum Root to Leaf Numbers(Java and Python)

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.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

When I met this question, I intuitively come out that recursion may be a good way to solve this problem. For a recursive solution, the base case is extremely important and it is always the key point to solve a question.

Depend on my experience, for a tree question, the root==null is always a base case, another base case in this question is decided when the node is a leaf node. Then we know that we can use root.left==null && root.right==null to represent this situation and it also should be a base case here. Once I found the base cases, we can just apply the DFS to track each path from root to leaf and update the sum variable. The reason I use an array to hold the same value is because Java can only passed by value. For example, 

in a=1; void calculate(int a){ a=a+1; } System.out.println(a); // the result is still 1 , not 2 In order to track sum value of each calculation and not return the value of sum, we should use a collection or a wrapper class to hold it  

So I use an array here to hold this sum value. If you anybody has another way to solve this problem, please leave a comment for me.

	/*
	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.
	For example,
	1
	/ \
	2 3
	The root-to-leaf path 1->2 represents the number 12.
	The root-to-leaf path 1->3 represents the number 13.
	Return the sum = 12 + 13 = 25.
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	/*
	When I met this question, I intuitively come out that recursion may be a good way to solve this problem.
	For a recurive solution, the base case is extremly important and it is always the key point to solve a question
	Depend on my experience, for a tree quesiton, the root==null is always a base case, another base case in this question
	is decide when the node is a leaf node. Then we know that we can use root.left==null && root.right==null to represent this
	situation and it also should be a base case here.
	Once I found the base cases, we can just apply the DFS to track each path from root to leaf and update the sum
	variable.
	the reason I use a array to hold the sum value is becasue Java can only pass by value. for example
	int a=1;
	void calculate(int a){
	a=a+1;
	}
	System.out.println(a); // the result is still 1 , not 2
	So,in order to track sum value of each calculation and not return the value of sum, we should use a collection
	or a wrapper class to hold it
	So I use a arry here to hold this sum value here
	if you any boday has other way to solve this problem please leave a comments for me.
	*/
	public class Solution {
	public int sumNumbers(TreeNode root) {
	if (root==null){
	return 0;
	}
	int[] sum={0};
	int current=0;
	getSum(root,current, sum);
	return sum[0];
	}
	public void getSum(TreeNode root, int current, int[] sum){
	if (root==null){
	return;
	}
	current=current*10+root.val;
	if (root.left==null && root.right==null){
	sum[0]=sum[0]+current;
	return;
	}
	getSum(root.left, current, sum);
	getSum(root.right, current, sum);
	}
	}

view raw SumRootTOLeafNum.java hosted with ❤ by GitHub

	"""
	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.
	For example,
	1
	/ \
	2 3
	The root-to-leaf path 1->2 represents the number 12.
	The root-to-leaf path 1->3 represents the number 13.
	Return the sum = 12 + 13 = 25.
	"""
	# Definition for a binary tree node
	# class TreeNode:
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None
	class Solution:
	# @param root, a tree node
	# @return an integer
	def sumNumbers(self, root):
	if not root:
	return 0
	current=0
	sum=[0]
	self.calSum(root, current, sum)
	return sum[0]
	def calSum(self, root, current, sum):
	if not root:
	return
	current=current*10+root.val
	if not root.left and not root.right:
	sum[0]+=current
	return
	self.calSum(root.left, current, sum)
	self.calSum(root.right,current, sum)

view raw SumRootToLeafNumbers.py hosted with ❤ by GitHub

Minimum Depth of Binary Tree (Python and Java)

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.

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	//new solution write at 3/5/2014
	public class Solution {
	public int minDepth(TreeNode root) {
	if (root==null){
	return 0;
	}
	if (root.left==null && root.right==null){
	return 1;
	}
	if (root.left!=null && root.right!=null){
	return 1+Math.min(minDepth(root.left), minDepth(root.right));
	}
	if (root.left==null){
	return 1+minDepth(root.right);
	}
	return 1+minDepth(root.left);
	}
	}
	"Be care of that is the current root is empty the already added depth should -1 and return "
	"Time Complexity is O(n)"
	public class Solution {
	public int minDepth(TreeNode root) {
	if (root == null){
	return 0;
	}
	else if (root.left==null && root.right==null){
	return 1;
	}
	return minDepthHelper(root, 1);
	}
	public int minDepthHelper(TreeNode root, int depth){
	if (root==null){
	// if the current root is null, then the depth should -1 and return;
	return depth-1;
	}
	int left=minDepthHelper(root.left, depth+1);
	int right=minDepthHelper(root.right, depth+1);
	// if left ==depth mean the left node is null, so return the right
	if (left==depth){
	return right;
	}
	// if rigth==depth mean the right node is null, so return left
	if (right==depth){
	return left;
	}
	return Math.min(left,right);
	}
	}

view raw Minimum Depth of Binary Tree.java hosted with ❤ by GitHub

	"""
	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.
	"""
	# Definition for a binary tree node
	# class TreeNode:
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None
	# Solution 1
	class Solution:
	def minDepth(self, root):
	if root==None:
	return 0
	if root.left==None and root.right==None:
	return 1
	depth=1
	return self.getMinDepth(root, depth)
	def getMinDepth(self, root, depth):
	if root==None:
	return depth-1
	leftDepth=self.getMinDepth(root.left, depth+1)
	rightDepth=self.getMinDepth(root.right, depth+1)
	# left side depth equal to current depth mean left side is None, so just rightDepth
	if leftDepth==depth:
	return rightDepth
	# same reason with above
	if rightDepth==depth:
	return leftDepth
	# not None for both side, we return the smalles one
	return min(leftDepth, rightDepth)
	# Solution 2
	class Solution:
	# @param root, a tree node
	# @return an integer
	def minDepth(self, root):
	if root==None:
	return 0
	if root.left==None and root.right==None:
	return 1
	if root.left!=None and root.right!=None:
	return min(self.minDepth(root.left), self.minDepth(root.right))+1
	if root.left!=None:
	return self.minDepth(root.left)+1
	return self.minDepth(root.right)+1

view raw MinimumDepthofBinaryTree.py hosted with ❤ by GitHub

Search in Rotated Sorted Array (Java+Python)

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.

       

Search a item in sorted array we should think about binary search. Cause the given array has been rotated unknow times, so binary search can not be apply directly here.

       

Throgh observation we can see, no matter how a sorted array be rotated, there is

 always one side is sorted.

       

So we can pick the middle item at first and compare it with given array's leftMost and rightMost items to check which side is sorted, for given example 4, 5 , 6, 7 , 0 , 1, 2

mid is 7, leftMost is 4, rightMost is 2, because of 4<7 so we can know left side is sorted.

       

Depend on the conclusion we got above, if the given target is between 4->7, such as 6, we can just seach left side for it, otherwise we search the right side.

       

A trick situation is when duplicate exist in the array, discard the requriement of this quesiton, my         solution will also cover duplicate exist situation. 

If duplicate exist, then leftMost or rightMost item may equal to middle item, if only one of them equal to mid such as A[leftMost]==A[mid] then from leftMost to Mid should have same value. then we can only search the right side from mid to right most. If both A[rightMost] and A[leftMost] equal to A[Mid] we have to search both sides.

	"This question usually asked in an interview with two step ."
	"1, Assume the num in the array is unique"
	"2, if the num is not unique how to implement and how the complexity will going?"
	"for unique array, it is relative simple in logic, but don’t happy so earlier,"
	"this detail implementation is not easy to handle cause of the boundary case".
	"First, when looked a question about search an item in an sorted array, you first idea is apply binary search,"
	"for this question, our basic strategy is also binary search, but cause of this sorted array has been rotated,"
	"so We have to check it the num we are search is in specific range(left half or right half),"
	"because it is a sorted array before rotated,so there must a half be sorted although the array has been rotated,"
	"then we check if the num we are looing is possible in the sorted half, if it is, then search it, else,"
	"search another side."
	"the time complexity is O(lgn), because it is just a binary search with check the sorted range,"
	"the check sorted range can be did just by compare the start point and the mid point"
	public class Solution {
	public int search(int[] A, int target) {
	int begin=0;
	int end=A.length-1;
	return searchHelper(A, begin,end,target);
	}
	public int searchHelper(int[] A, int begin, int end, int target){
	if (begin>end) return -1;
	if (begin==end) {
	if (target==A[begin]){
	return begin;
	}
	else {
	return -1;
	}
	}
	int mid=(begin+end)/2;
	if (A[mid]==target) return mid;
	if(A[begin]<A[mid]){
	if (A[begin]<=target && target<A[mid]){
	return searchHelper(A,begin, mid, target);
	}
	else{
	return searchHelper(A, mid, end, target);
	}
	}
	else if (A[mid]<A[begin]){
	if (A[mid]<target && target<=A[end]){
	return searchHelper(A,mid,end, target );
	}
	else{
	return searchHelper(A, begin, mid, target);
	}
	}
	else{
	return searchHelper(A,mid+1, end, target);
	}
	}
	}
	"Then let's talk the the situation that if the array contain duplicate items"
	"In this situation, the only difference is the left point equal to mid point, under this situation , "
	"if mid point not equal to right, then we can just search the mid -> right range, or we have to search both side, "
	"example(2,2,4,6,8 and 2,2,2,4,7,8,2,2)"
	"because of the potential situation to search both side, so the time complexity is O(n) in worst case."
	public class Solution {
	public int search(int[] A, int target) {
	if(A==null ||A.length==0){
	return -1;
	}
	int st=0;
	int ed=A.length-1;
	return search(A, st, ed, target);
	}
	public int search(int[] A, int st, int ed, int target){
	if (st>ed){
	return -1;
	}
	int mid=st+(ed-st)/2;
	if (A[mid]==target){
	return mid;
	}
	if (A[st]<A[mid]){
	if (target>=A[st] && target<A[mid] ){
	return search(A, st, mid-1, target);
	}
	return search(A, mid+1, ed, target);
	}
	else if (A[st]>A[mid]){
	if (A[mid]<target && target<=A[ed]){
	return search(A, mid+1, ed, target);
	}
	return search(A, st, mid-1, target);
	}
	else{
	if (A[mid]!=A[ed]){
	return search(A, mid+1, ed, target);
	}
	else{
	int result=search(A, st, mid-1, target);
	if (result!=-1){
	return result;
	}
	return search(A, mid+1, ed, target);
	}
	}
	}
	}

view raw SearchInRotatedSortedArray.java hosted with ❤ by GitHub

	class Solution:
	# @param A, a list of integers
	# @param target, an integer to be searched
	# @return an integer
	def search(self, A, target):
	if A==None or len(A)==0:
	return -1;
	st=0;
	ed=len(A)-1
	return self.searchHelper(A, target, st, ed)
	def searchHelper(self, A, target, st, ed):
	if st>ed:
	return -1
	mid=(st+ed)/2
	if A[mid]==target:
	return mid
	if A[st]<A[mid]:
	if A[st]<=target<A[mid]:
	return self.searchHelper(A, target, st, mid-1)
	return self.searchHelper(A, target, mid+1, ed)
	elif A[st]>A[mid]:
	if A[mid]<target<=A[ed]:
	return self.searchHelper(A, target, mid+1, ed)
	return self.searchHelper(A, target, st, mid-1)
	else:
	if A[mid]!=A[ed]:
	return self.searchHelper(A, target, mid+1, ed)
	result=self.searchHelper(A, target, st, mid-1)
	if result!=-1:
	return result
	return self.searchHelper(A, target, mid+1, ed)

view raw SearchInRotatedSortedArray.py hosted with ❤ by GitHub

Trapping Rain Water (Java + Python)

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Solution: DP 

 To calculate the total volume is to calculate volumes can hold at each position.

 To calculate how many volumes can hold at each position is to calculate it's right bound height  and right bound height 

Current position can hold water only at the situation when the low side among both sides higher than the height at current position

If so,  use the lower one minus current height as height to multiply the width 1 is how many volumes can hold at current position

How to calculate the height of both sides for each position? We can apply DP theory to record  highest height bound can get from left to current and highest height bound can get from right to current  

HigehstLeftSideHeight so far from giving example, should be  0,1,1,2,2,2,2,3,3,3,3,3

HighestRightSideHeight so far for given example is 1,2,2,2,3,3,3,3,3,3,3,3

Then loop through giving array for each position to calculate how many volumes can hold there and update the total volume it can hold

	/*
	Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
	For example,
	Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
	// To calculate the total volume is to calculate volume can hold at
	// each position.
	// To calculate how many volume can hold at each position is to calculate it's right bound height
	// and right bound height
	//Current position can hold water only at situation when the lowest side among both sides higher than the height at current position
	//if so, use the lower one minues current height as height to multily the width 1 is how many volume can hold at current position
	// How to calculate the height of both sides for each position? we can apply DP theory
	// to record hightest height bound can get from left to current and highest height bound can get from right to current
	// HigehstLeftSideHeight so far for given example should be
	// 0,1,1,2,2,2,2,3,3,3,3,3
	// HighestRightSideHeight so far for given example is
	// 1,2,2,2,3,3,3,3,3,3,3,3
	// then loop through given array for each posiiton calculate how many volume can hold there and update the total voluem it can hold
	*/
	public class Solution {
	public int trap(int[] A) {
	if (A==null ||A.length==0){
	return 0;
	}
	int[] highestLeftSoFar=new int[A.length];
	int[] highestRightSoFar=new int[A.length];
	// left->right
	for (int i=0; i<highestLeftSoFar.length; i++){
	highestLeftSoFar[i]=i==0?A[i]:Math.max(A[i], highestLeftSoFar[i-1]);
	}
	// right -> left
	for (int i=A.length-1; i>=0; i--){
	highestRightSoFar[i]=i==A.length-1?A[i]:Math.max(A[i], highestRightSoFar[i+1]);
	}
	int totalVolume=0;
	for (int i=0; i<A.length; i++){
	int height=Math.min(highestLeftSoFar[i], highestRightSoFar[i]);
	if (height>A[i]){
	height=height-A[i];
	totalVolume+=height*1;
	}
	}
	return totalVolume;
	}
	}

view raw TrappingRainWater.java hosted with ❤ by GitHub

	"""
	Given n non-negative integers representing an elevation map where the width of each bar is 1,
	compute how much water it is able to trap after raining.
	For example,
	Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
	The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1].
	In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
	"""
	class Solution:
	# @param A, a list of integers
	# @return an integer
	def trap(self, A):
	if not A:
	return 0
	highestLeftSoFar=[]
	highestRightSoFar=[]
	for i in range(len(A)):
	highestLeftSoFar.append(A[i] if i==0 else max(A[i], highestLeftSoFar[-1]))
	for i in range(len(A)-1, -1, -1):
	highestRightSoFar.insert(0,A[i] if i==len(A)-1 else max(A[i], highestRightSoFar[0]))
	totalVolume=0;
	for i, currentHeight in enumerate(A):
	minSideHeight=min(highestLeftSoFar[i], highestRightSoFar[i])
	if minSideHeight>currentHeight:
	totalVolume+=(minSideHeight-currentHeight)*1
	return totalVolume

view raw TrappingRainWater.py hosted with ❤ by GitHub