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

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

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.

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.

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.

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