Leetcode - Permutation Palindrome ii (javascript)

 267. Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Analysis:
1. start from i, first figure out if s is valid for palindrome by checking if have > 1 odd # letter. Use a map to record key-count.
2. If valid, reduce all even count/=2. If find the odd one, reduce to 0, and save odd letter.
3. DFS the left half till reach s.length/2, append to res with odd + reverse right half.

Complexity:
Time O(N!)

var s = "aasbb";
var map = {};
var res = [];
var odd = "";
if (helper(s, map)) {
    for (var key in map) {
        if (map[key] === 1) {
            odd = key;
            delete map[key];
        }
        if (map[key] % 2 === 0) {
            map[key] /= 2;
        }
    }
    dfs(map, [], res, parseInt(s.length / 2), odd);
}
console.log(res);//["absba", "basab"]

function dfs(map, path, res, len, odd) {;
    if (path.length === len) {
        res.push(path.join("") + odd + path.reverse().join(""));
        return;
    }
    for (var key in map) {
        if (map[key] === 0) {
            continue;
        }
        path.push(key);
        map[key]--;
        dfs(map, path, res, len, odd);
        path.pop();
        map[key]++;
    }
}

function helper(s, map) {
    var count = 0;
    for (var i = 0; i < s.length; i++) {
        if (map[s[i]] === undefined) {
            map[s[i]] = 0;
        }
        map[s[i]]++;
    }
    for (var key in map) {
        if (map[key] % 2 !== 0) {
            count++;
        }
        if (count > 1) {
            return false
        }
    }
    return true;
}

Leetcode -- 547. Friend Circles(dfs)

547. Friend Circles(dfs)
medium
https://leetcode.com/problems/friend-circles/#/description

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are directfriends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:

Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.

Example 2:

Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:

1. N is in range [1,200].
2. M[i][i] = 1 for all students.
3. If M[i][j] = 1, then M[j][i] = 1.

思路：- define visited array for each person, mark all ppl in one cycle visited using dfs
           - traverse the he specific row, if get 1, traverse the corresponding row of that column #
             since 2's friend is considered indirect friend of 1
           - once finishing visit a 1 cycle, increment circle res

Complexity: Time O(N^2) -- n cycle  Space O(1)

public class Solution {
    public int findCircleNum(int[][] M) {
        boolean visited[] = new boolean[M.length];
        int cycle = 0;
        for(int i = 0; i < M.length; i ++){
            if(!visited[i]){
                cycle++;
                visited[i] = true;
                dfs(M, visited, i);//dfs to mark all ppl in the cycle visited
            }
        }
        return cycle;
    }
    public void dfs(int[][] M, boolean[] visited, int i){
        for(int j = 0; j < M[0].length; j++){//no return case here!!
            if(!visited[j] && M[i][j] == 1){
                visited[j] = true;
                dfs(M, visited, j);
            }
        }
    }
}

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 -- 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/G家F家苹果-- 257. Binary Tree Paths(DFS)

257. Binary Tree Paths(dfs)

Easy

https://leetcode.com/problems/binary-tree-paths/

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

 Google Apple Facebook

思路： use dfs to traverse tree, append val to stringbuilder, add string to res when meeting root.
Complexity: Time: O(n), Space: O(n) -arraylist
way1 - stringbuilder

public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        helper(root, res, new StringBuilder());
        return res;
    }
    public void helper(TreeNode root, List<String> res, StringBuilder s){
        if(root == null)return;
        int len = s.length();
        s.append(root.val).append("->");
        if(root.left == null && root.right == null){
            res.add(s.toString().substring(0, s.length()-2));//remove last "->"
        }
        helper(root.left, res, s);
        helper(root.right, res, s);
        s.setLength(len);
    }

way2 - string

public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String> ();
        if(root == null){ return res;}
        String cur = new String("");
        addpath(root, res, cur);
        return res;
    }
    private void addpath(TreeNode root,List<String> res,String cur){
        if(root == null){
            return;
        }
        cur += Integer.toString(root.val);
        cur += "->";//string + opperation no need to set back length
        if(root.left==null&&root.right==null){
            cur = cur.substring(0,cur.length()-2);
            res.add(cur);
        }
        addpath(root.left,res,cur);
        addpath(root.right,res,cur);
    }

Leetcode/亚麻 -- 199. Binary Tree Right Side View (BFS + DFS)

199. Binary Tree Right Side View (BFS + DFS)
medium
https://leetcode.com/problems/binary-tree-right-side-view/

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

思路1： BFS, use level order traverlsal. key is to track each level size, and add the 1ast one to list.

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> qu = new LinkedList<>();
        if(root == null) return res;
        qu.offer(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            for(int i = 0; i < size; i++){//traveling current level
                TreeNode curr = qu.remove();
                if(i == size - 1)res.add(curr.val);
                if(curr.left != null) qu.offer(curr.left);
                if(curr.right != null) qu.offer(curr.right);
            }
        }
        return res;
    }

思路2: DFS， preorder改一下顺序，从右走的左边. To ensure rightmost node of depth,
            Key is we ensure we only add the first node of the specific depth by check depth == list size.
for ex, if we add node at depth 1 from right subtree, we won't add it again when travel the left subtree

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        traverse(root, result, 0);
        return result;
    }
    public void traverse(TreeNode root, List<Integer> result, int depth){
        if(root == null)return;
        if(depth == result.size()){
            result.add(root.val);
        }
        traverse(root.right, result, depth + 1);
        traverse(root.left, result, depth + 1);
    }

Leetcode/微软bloogberg -- 112.113.Path Sum I + II(dfs)

112.113. Path Sum I/II (Backtracking)
easy medium
https://leetcode.com/problems/path-sum/
https://leetcode.com/problems/path-sum-ii/
相关题 Path III，区别在于path可以树中任意路径上的节点，所以2次dfs，多的一次用来计算树中非root的pathSum http://rainykat.blogspot.com/2017/01/leetcode-437-path-sum-iii-2dfs.html

113.

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

112只要返回有无路径,return true or false

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null)return false;
        if(root.left == null && root.right == null && sum - root.val == 0)
            return true;
        return hasPathSum(root.left, sum - root.val)||hasPathSum(root.right, sum - root.val);
    }
}

113需要存下path, back track path

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null)return res;
        helper(root, res, new ArrayList<Integer>(), sum);
        return res;
    }
    public void helper(TreeNode root, List<List<Integer>> res, List<Integer> path, int sum){
        if(root == null)return;
        path.add(root.val);
        if(root.left == null && root.right == null && sum - root.val == 0)
            res.add(new ArrayList<>(path));
        helper(root.left, res, path, sum - root.val);
        helper(root.right, res, path, sum - root.val);
        path.remove(path.size()-1);
    }
}

Leetcode -- 437. Path Sum III (2DFS)

437. Path Sum III
Easy
https://leetcode.com/problems/path-sum-iii/

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

思路： do two recursion. different from pathSumII that start can be any node, so we have 1st recur.
1st： recursively travel tree to find answers of current node + ans of left child + ans of right child.
2nd: find the path from current node to child that adds up to sum
Complexity: 

If the tree is balanced, then each node is reached from its ancestors (+ itself) only, which are up to log n. Thus, the time complexity for a balanced tree is O (n * log n).

However, in the worst-case scenario where the binary tree has the same structure as a linked list, the time complexity is indeed O (n ^ 2)

O(H) space - height of binary tree

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null)return 0;
        return helper(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
        //so total count will be countOf(hasRoot) + countOf(leftChild) + countOf(rightChild) 
    }
    public int helper(TreeNode root,int sum){
        int count  = 0;
        if(root == null)return 0;
        if(root.val - sum == 0)count++;
        count += helper(root.left, sum - root.val);
        count += helper(root.right, sum - root.val);
        return count;
    }
}

 

Version2 more comprehensive

public class Solution {
    int count = 0;
    public int pathSum(TreeNode root, int sum) {
        if (root == null)return 0;
        helper(root,sum);
        pathSum(root.left,sum);
        pathSum(root.right,sum);
        return count;
    }
    public void helper(TreeNode root,int sum){
        if(root == null)return;
        if(root.val - sum == 0)count++;
        helper(root.left, sum - root.val);
        helper(root.right, sum - root.val);
    }
}