Minimum Depth of Binary Tree

This problem gave me a hard time, basically what I missed is that the definition of the minimum depth. It should be “the shortest path from the root node down to the nearest leaf node.” Therefore if there is only a root and a node attached to it, the minimum depth will be 2 instead of 1.

The idea is recursion. Basically what I was thinking is do a tree traverse while keeping the minimum value, this is affected by the pocket algorithm I currently am studying. It turned out to be a much more effective way to do this.

 


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        return recursionStep(root);
    }
    
    public static int recursionStep(TreeNode root){
        
        if(root == null) return 0;
        
        int left = recursionStep(root.left);
        int right = recursionStep(root.right);
        
        //to the nearest leaf node!!!
        
        if(left == 0) return right+1;
        if(right == 0) return left+1;
        
        return left < right? left+1 : right+1;
    }
}

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

This is not the best solution but still O(n) time, also it is only one iteration, which is the try to part of the note.


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        if(head == null || (head.next == null && n == 1)){
            return null;
        }
        
        ArrayList bucket = new ArrayList();
        
        ListNode position = head;
        
        while(position != null){
            bucket.add(position);
            position = position.next;
        }
        
        int length = bucket.size();
        
        if(length-n <= 0){
            head = head.next;
        }else if(bucket.get(length-n) == null || bucket.get(length-n).next == null){
            bucket.get(length-n-1).next = null;
        }else{
            bucket.get(length-n-1).next = bucket.get(length-n+1);
        }
        
        return head;
        
    }
}