83.82.Remove Duplicates from Sorted List I/II (recur)

83.82. Remove Duplicates from Sorted List(Recur)
easy/ medium

83. https://leetcode.com/problems/remove-duplicates-from-sorted-list/#/description

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

思路： Two methods, 1. from end to start, skip each dup node (in summary)
           2. in return case, skip dup node & keep calling next deleteDup function

Complexity: Time O(n) Space O(1)

public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)return head;
        if(head.val == head.next.val){
            while(head.next != null && head.val == head.next.val){
                head = head.next;
            }
            //think it as return head.next, so we retain one dup node
            return deleteDuplicates(head);
            //once return, will perform code after the below recursive call, so we call recursive again here
        }
        head.next = deleteDuplicates(head.next);
        return head;
    }

82. https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/#/description

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

 思路： Use recursion, in return case, skip dup node & keep calling next deleteDup function

Complexity: Time O(n) Space O(1)

public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)return head;
        if(head.val == head.next.val){
            while(head.next != null && head.val == head.next.val){
                head = head.next;
            }
            //think it as return head.next, so we skip the dup one
            return deleteDuplicates(head.next);
            //once return, will perform code after the below recursive call, so we call recursive again here
        }
        head.next = deleteDuplicates(head.next);
        return head;
    }

Leetcode/G家F家 -- 341. Flatten Nested List Iterator (Design + Recur)

341. Flatten Nested List Iterator(Design + Recur)
medium
https://leetcode.com/problems/flatten-nested-list-iterator/
相关题： 同样用recursion traverse list 来计算
http://rainykat.blogspot.com/2017/01/leetcodelinkedin-339364-nested-list.html 

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

 Google Facebook Twitter

思路： traverse the nested list using recursion and store element to arraylist.

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    List<Integer> list = new ArrayList<>();
    int pos = 0;//current position
    public NestedIterator(List<NestedInteger> nestedList) {
        //use arrayList to store nestedList
        traverse(nestedList);
    }
    public void traverse(List<NestedInteger> nestedList){
        if(nestedList == null) return;
        for(NestedInteger e: nestedList){
            if(e.isInteger()){
                list.add(e.getInteger());
            }else{
                traverse(e.getList());//do recursion when meeting list element
            }
        }
    }
    @Override
    public Integer next() {
        return list.get(pos++);
    }

    @Override
    public boolean hasNext() {
        return pos < list.size();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

Leetcode -- 226. Invert Binary Tree(Recur + Itera)

226. Invert Binary Tree(Recur + Itera)
easy
https://leetcode.com/problems/invert-binary-tree/?tab=Description

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

思路1： Recursion - when meeting null or leaf nodes, we don't swap.
           Then we keep swaping the left subtree and right subtree (1. traverse 2. reassign value)
Complexity: time O(N) space O(H)
        

public TreeNode invertTree(TreeNode root) {
        if(root == null)return null;
        if(root.left == null && root.right == null)return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

思路2： Iteration - level order traverse. keep swaping left child and right child of current node

public TreeNode invertTree(TreeNode root) {
        if(root == null)return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            TreeNode left = cur.left;
            TreeNode right = cur.right;
            cur.left = right;
            cur.right = left;
            if(right != null)q.offer(right);//here order not matter
            if(left != null)q.offer(left);
        }
        return root;
    }

Leetcode/各大家 -- 230. Kth Smallest Element in a BST(Recur + Ite)

230. Kth Smallest Element in a BST (Recur + Itera)
medium

Given a binary search tree, write a function kthSmallest to find the kth 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?

Bloomberg Uber Google

思路1： using inorder traversal by recursion, keep a global var count to track kth element.
Inorder we will first get the min(leftmost node), then 2nd min (parent node of min),
then 3rd min(right node of 2nd min)....
Complexity: O(N) - time O(N) - stack

public class Solution {
    int count = 0;
    int result = -1;
    public int kthSmallest(TreeNode root, int k) {
        traverse(root, k);
        return result;
    }
    public void traverse(TreeNode root, int k) {
        if(root == null) return;
        traverse(root.left, k);
        count++;
        if(count == k)
            result = root.val;
        traverse(root.right, k);
    }    
}

思路2： using iteration to store the path to current min node into a stack.
When we pop node, we check if it has left node and add till the leftmost node all the way to leftmost.

public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> st = new LinkedList<>();
        int res = 0;
        while(root != null){//find the min - leftmostnode
            st.push(root);
            root = root.left;
        }
        while(!st.isEmpty() && k > 0){
            TreeNode cur = st.pop();
            res = cur.val;
            k--;
            cur = cur.right;
            while(cur != null){//keep adding till the leftmost node of right node
                st.push(cur);
                cur = cur.left;
            }
        }
        return res;
    }

Leetcode/各大家 -- 101. Symmetric Tree(Recur + Itera)

101. Symmetric Tree (Recursion + Iteration)


easy
https://leetcode.com/problems/symmetric-tree/

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

LinkedIn Bloomberg Microsoft



思路： use recursion to recursively find if nodes in left & right subtree match till leaves.
               helper(left.left ,right.right) && helper(left.right, right.left);

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null)return true;
        return helper(root.left, root.right);
    }
    private boolean helper(TreeNode leftN, TreeNode rightN){
        if(leftN == null || rightN == null)
            return leftN == rightN;//need both be null
        if(leftN.val != rightN.val)
            return false;
        return helper(leftN.left, rightN.right) && helper(leftN.right, rightN.left);
    }
}

Leetcode/微软 -- 116. Populating Next Right Pointers in Each Node(Recur + Iterat)

116. Populating Next Right Pointers in Each Node(Recursion+ Iteration)
medium
https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

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).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

思路1： use recursion,
Complexity: O(n)time  --  visit each node to set up next pointer.
                     O(logN) space -- each node up to logN nodes from ancestor to itself

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null)return;
        if(root.left != null){
            root.left.next = root.right;
            if(root.next != null){
                root.right.next = root.next.left;//perfect binary tree, no check if root.right is null
            }
        }
        connect(root.left);
        connect(root.right);
    }
}

思路2: Iterative, need to check cur.next is null, eg rightmost node on level
Complexity: O(N)-time O(1)-space

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null)return;
        TreeLinkNode level_start=root;
        while(level_start != null){
            TreeLinkNode cur=level_start;
            while(cur != null){
                if(cur.left != null)cur.left.next = cur.right;
                if(cur.right != null && cur.next != null)cur.right.next = cur.next.left;
                cur = cur.next;
            }
            level_start = level_start.left;
        }
    }
}

Leetcpde -- 263.264 Ugly Number(Recur) + II(DP)

263.264 Ugly Number + II
easy/medium

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

263 I. only need to decide if ugly number, return true/false.
思路： keep mod and divide 2,3,5 till base case.

public class Solution {
    public boolean isUgly(int num) {
        if(num <= 0) return false;
        if(num == 1) return true;
        if(num%2 == 0){
            return isUgly(num/2);
        }
        if(num%3 == 0){
            return isUgly(num/3);
        }
        if(num%5 == 0){
            return isUgly(num/5);
        }
        return false;
    }
}

264 II.
思路1： use dp[n] to track next ugly number

public class Solution {
    public int nthUglyNumber(int n) {
        int i1 = 0, i2 = 0, i3 = 0;
        int num1 = 2,num2 = 3,num3 = 5;//ugly number: 1,2,3,5,
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            dp[i] = Math.min(num1, Math.min(num2, num3));
            if(dp[i] == num1){
                i1++;
                num1 = 2*dp[i1];
            }
            if(dp[i] == num2){
                i2++;
                num2 = 3*dp[i2];
            }
            if(dp[i] == num3){
                i3++;
                num3 = 5*dp[i3];
            }
        }
        return dp[n-1];
    }
}

思路2： use heap to return the min, keep adding min*2, min*3, min*5 and minus n, till n == 0
slow

ublic class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        long res = 0;
        heap.add((long)1);
        while(!heap.isEmpty() && n > 0){
            while(res == heap.peek()){
                heap.poll();
                continue;
            }
            res = heap.poll();
            heap.add(res * 2);
            heap.add(res * 3);
            heap.add(res * 5);
            n--;
        }
        return (int)res;
    }
}

Leetcode/Linkedin -- 156. Binary Tree Upside Down (Recur+Itera)

156. Binary Tree Upside Down(Recursion + Iteration)
medium
https://leetcode.com/problems/binary-tree-upside-down/

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1  

思路1：Recursion, find the leftmost node as the root. Return repoint each new parent - root.left to previous root and root.right;
Complexity: O(N)time, O(N)space stack

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root == null || root.left == null)return root;
        TreeNode newRoot = upsideDownBinaryTree(root.left);
        //root.left is newRoot everytime
        root.left.left = root.right;
        root.left.right = root;
        root.left = null;
        root.right = null;
        return newRoot;
    }
}

思路2: Iterative, pre is previous root after repoint, use tmp to track the right node of previous root.
Complexity: O(N)time O(1)space

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode cur = root;
        TreeNode pre = null;
        TreeNode tmp = null;
        TreeNode next = null;
        while(cur != null){
            next = cur.left;
            //need tmp to keep the previous right child
            cur.left = tmp;
            tmp = cur.right;
            
            cur.right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}