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 -- 143. Reorder List(LinkedList)

143. Reorder List
medium
https://leetcode.com/problems/reorder-list/#/description

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

思路： Three steps
           1. Find the middle of list
           2. Reverse the last half o list (from the next one of middle)
           3. Connect 1st half and 2nd half iteratively

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

public void reorderList(ListNode head) {
        if(head == null)return;
        ListNode slow = head;
        ListNode fast = head;
        
        //1. find the middle of list
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow.next;//2nd half start from next node of the middle one
        slow.next = null;
        
        //2. reverse last half of list
        ListNode newHead = reverseList(tmp);
        
        //3. connect 1st half to 2nd half
        ListNode cur = head;
        while(cur != null && newHead != null){
            ListNode tmp1 = cur.next;
            ListNode tmp2 = newHead.next;
            cur.next = newHead;
            newHead.next = tmp1;
            cur = tmp1;
            newHead = tmp2;
        }
    }
    
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){ return head;}
        ListNode nextN = head.next;
        head.next = null;
        while(nextN != null){
            ListNode tmp = nextN.next;
            nextN.next = head;
            head = nextN;
            nextN = tmp;
        }
        return head;
    }

Leetcode -- 129. Sum Root to Leaf Numbers(dfs)

129. Sum Root to Leaf Numbers(dfs)
medium
https://leetcode.com/problems/sum-root-to-leaf-numbers/#/description

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.

思路： - Using dfs, add left path & right path to current node for getting number till reach the leaf.
           Calculate by sum = root.val + sum*10;
           - Since we calculate left & right with same previous sum(parent node), so we do
            recursive call: helper(root.left, sum) + helper(root.right, sum);

Complexity： Time O(n) Space O(h)

public class Solution {
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }
    public int helper(TreeNode root, int sum){
        if(root == null) return 0;
        if(root.left == null && root.right == null)
            return root.val + sum*10;
        sum = root.val + sum*10;
        return helper(root.left, sum) + helper(root.right, sum);
    }
}

Leetcode/微软百度 -- 124. Binary Tree Maximum Path Sum(DFS)

124. Binary Tree Maximum Path Sum(DFS)
Hard
https://leetcode.com/problems/binary-tree-maximum-path-sum/#/description

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

思路： At every node, the max path formed by node's val + left child path (>0) + right child path(>0)
          Since we can only have 1 parent node in path, when we do recursive call,
          - in helper: for each child node, we add the node's val with either its left or right path or nothing.
          - keep track the max vs path sum pass through current node as the parent node

Complexity：  Time O(n) Space O(h)

public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    //Path pass parent node only once
    //at every node, either add its left or right path or nth for n
    public int helper(TreeNode root){
        if(root == null) return 0;
        int sum1 = Math.max(0, helper(root.left));
        int sum2 = Math.max(0, helper(root.right));
        max = Math.max(max, sum1 + sum2 + root.val);
        return root.val + Math.max(sum1, sum2);
    }
}

Leetcode -- 103. Binary Tree Zigzag Level Order Traversal (BFS)

103. Binary Tree Zigzag Level Order Traversal (BFS)
medium
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/#/description

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

思路： just like level order traversal, but we travel the tree in Z shape.
          So any even row, the order of nodes in the row will be reversed when adding to the result arraylist: Collections.reverse(res.get(level))

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

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> q = new LinkedList();
        int level = 0;
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            res.add(new ArrayList());
            for(int i = 0; i < size; i++){
                TreeNode cur = q.poll();
                res.get(level).add(cur.val);
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
            }
            if(level%2 == 1)
                Collections.reverse(res.get(level));
            level++;
        }
        return res;
    }

Leetcode -- 508. Most Frequent Subtree Sum(DFS)

508. Most Frequent Subtree Sum(DFS)
Medium
https://leetcode.com/problems/most-frequent-subtree-sum/?tab=Description

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1
Input:

  5
 /  \
2   -3

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2
Input:

  5
 /  \
2   -5

return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

思路： Use HashMap + PostOrder DFS tree traversal.
Complexity: Time: O(N) - tree traversal, Space: O(N) - map

public class Solution {
    Map<Integer, Integer> map = new HashMap();
    int maxCount = 0;
    public int[] findFrequentTreeSum(TreeNode root) {
        //use DFS
        List<Integer> tmp = new ArrayList();
        helper(root);
        for(Integer k:map.keySet()){
            if(map.get(k) == maxCount) tmp.add(k);
        }
        int[] res = new int[tmp.size()];
        int i = 0;
        for(Integer v:tmp){
            res[i++] = v;
        }
        return res;
    }
    
    public int helper(TreeNode root){
        if(root == null) return 0;
        int sum = root.val;
        sum += helper(root.left);
        sum += helper(root.right);
        if(!map.containsKey(sum)) map.put(sum, 0);
        map.put(sum, map.get(sum) + 1);
        maxCount = Math.max(maxCount, map.get(sum));
        return sum;
    }
}

Leetcode/各大家 -- 147. Insertion Sort List

147. Insertion Sort List（2 Ptr）
Medium
https://leetcode.com/problems/insertion-sort-list/?tab=Description
Sort a linked list using insertion sort.

思路： Use dummy head to point sorted list. Maintain 2 parts: sorted | unsorted.
          Use 2 ptr(cur-> current element & pre -> end of sorted list). When meeting invalid cur,
          Insert cur into sorted list by comparing with dummy head

Complexity: Time O(N^2) Space O(1)

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode pre = head;
        ListNode cur = head;
        dummy.next = pre;
        while(cur != null){
            if(pre.val > cur.val){
                pre.next = cur.next;
                ListNode headN = dummy;
                while(headN.next != null && headN.next.val < cur.val){
                    headN = headN.next;
                }
                cur.next = headN.next;
                headN.next = cur;
                cur = pre.next;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}