Graph: Depth First Search

Bottom up for O(N) Solution

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Naive O(N^2) Solution is:

class solution {
public:
    int depth (TreeNode *root) {
        if (root == NULL) return 0;
        return max (depth(root -> left), depth (root -> right)) + 1;
    }

    bool isBalanced (TreeNode *root) {
        if (root == NULL) return true;

        int left=depth(root->left);
        int right=depth(root->right);

        return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

Bottom Up O(N) Solution is:

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        bool isbalance = true;
        return -1 != get_height(root, isbalance);
    }

    int get_height(TreeNode* root, bool& isbalance) {
        if (!isbalance) return -1;
        if (!root) return 0;
        int left = get_height(root->left, isbalance);
        int right = get_height(root->right, isbalance);
        if (left == -1 || right == -1 || abs(left - right) > 1) {
            isbalance = false;
            return -1;
        }
        return 1 + max(left, right);
    }
};

124. Binary Tree Maximum Path Sum

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 does not need to go through the root.

For example: Given the below binary tree,

       1
      / \
     2   3

Return 6.

class Solution {
    int maxToRoot(TreeNode *root, int &re) {
        if (!root) return 0;
        int l = maxToRoot(root->left, re);
        int r = maxToRoot(root->right, re);
        if (l < 0) l = 0;
        if (r < 0) r = 0;
        if (l + r + root->val > re) re = l + r + root->val;
        return root->val += max(l, r);
    }
public:
    int maxPathSum(TreeNode *root) {
        int res = INT_MIN;
        maxToRoot(root, res);
        return res;
    }
};

111. Minimum Depth of Binary Tree

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.

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        int left = INT_MAX, right = INT_MAX;
        if (root->left) left = minDepth(root->left);
        if (root->right) right = minDepth(root->right);
        int cur_min = min(left, right);
        return cur_min + 1;
    }
};

Pre-order Traversal

114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

本质上是 preorder Traversal

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        TreeNode* p = root;
        while (p) {
            if (p->left) {
                TreeNode* tmp = p->right;
                TreeNode* tail = p->left;
                while (tail && tail->right) tail = tail->right;
                tail->right = tmp;
                p->right = p->left;
                p->left = nullptr;
            }
            p = p->right;
        }
    }
};

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        auto left = root->left;
        auto right = root->right;
        if (pre) {
            pre->left = nullptr;
            pre->right = root;
        }
        pre = root;
        flatten(left);
        flatten(right);
    }
private:
    TreeNode* pre = nullptr;
};

Inorder Traversal

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right && root->val == sum) return true;

        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

Iterative Solution:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        stack<TreeNode*> st;
        int cur_sum = 0;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        while (cur || !st.empty()) {
            while (cur) {
                st.push(cur);
                cur_sum += cur->val;
                cur = cur->left;
            }
            cur = st.top();

            if (!cur->left && !cur->right && cur_sum == sum) return true;

            if (cur->right && pre != cur->right) cur = cur->right;
            else { // no right child or finished visit right child, pop cur
                pre = cur;
                cur_sum -= cur->val;
                cur = nullptr;
                st.pop();
            }
        }

        return false;
    }
};

306. Additive Number

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example: "112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 "199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199. 1 + 99 = 100, 99 + 100 = 199 Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.

Follow up: How would you handle overflow for very large input integers?

class Solution {
public:
    bool isAdditiveNumber(string num) {
        if (num.size() < 3) return false;
        for (int i = 1; i <= num.size()/2; ++i) {
            for (int j = 1; j <= num.size()/2; ++j) {
                auto num1 = num.substr(0, i);
                if (num1.size() > 1 && num1[0] == '0') continue;
                auto num2 = num.substr(i, j);
                if (num2.size() > 1 && num2[0] == '0') continue;
                if (isAdditiveNumber(num, num1, num2, j+i)) return true;
            }
        }

        return false;
    }

    bool isAdditiveNumber(const string& num, string num1, string num2, int start) {
        string sum = to_string(stol(num1) + stol(num2));
        if (start + sum.size() > num.size() || sum != num.substr(start, sum.size())) return false;
        if (start + sum.size() == num.size()) return true;
        return isAdditiveNumber(num, num2, sum, start + sum.size());
    }
};

329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4 The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int res = 0;
        size_t m = matrix.size();
        if (!m) return res;
        size_t n = matrix[0].size();
        if (!n) return res;
        vector<vector<int>> visited(m, vector<int>(n, -1));

        for (size_t i = 0; i < m; ++i) {
            for (size_t j = 0; j < n; ++j) {
                res = max(res, dfs(matrix, visited, i, j));
            }
        }
        return res;
    }

    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int i, int j) {
        if (i < 0 || i >= matrix.size() || j < 0 || j >= matrix[0].size())
            return 0;
        if (visited[i][j] != -1) return visited[i][j];

        int result = 0;
        if (i > 0 && matrix[i][j] < matrix[i-1][j]) {
            result = max(result, dfs(matrix, visited, i-1, j));
        }
        if (i < matrix.size() - 1 && matrix[i][j] < matrix[i+1][j]) {
            result = max(result, dfs(matrix, visited, i+1, j));
        }
        if (j > 0 && matrix[i][j] < matrix[i][j-1]) {
            result = max(result, dfs(matrix, visited, i, j-1));
        }
        if (j < matrix[0].size() - 1 && matrix[i][j] < matrix[i][j+1]) {
            result = max(result, dfs(matrix, visited, i, j+1));
        }
        result += 1;
        visited[i][j] = result;
        return result;
    }
};

337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

   3
  / \
 2   3
  \   \ 
   3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

Solution needs to be improved

class Solution {
public:
    int rob(TreeNode* root) {
        unordered_map<TreeNode*, unordered_map<bool, int>> memo;
        return max(max_rob(root, true, memo), max_rob(root, false, memo));
    }

    int max_rob(TreeNode* root, bool parent_robbed, unordered_map<TreeNode*, unordered_map<bool, int>>& memo) {
        if (!root) return 0;
        if (memo.find(root) != memo.end() && memo[root].find(parent_robbed) != memo[root].end()) return memo[root][parent_robbed];

        int not_rob = max_rob(root->left, false, memo) + max_rob(root->right, false, memo);
        if (parent_robbed) {
            memo[root][parent_robbed] = not_rob;
            return not_rob;
        }
        int rob = max_rob(root->left, true, memo) + max_rob(root->right, true, memo);
        memo[root][parent_robbed] = max(root->val + rob, not_rob);
        return memo[root][parent_robbed];
    }
};

short and clean solution

lm is the max rob value of node->left rm is the max rob value of node->right lm1 is the max rob value of node->left->left (Same as lm2) rm1 is the max rob value of node->left->right (Same as rm2) So the max rob value of node is the max value between (lm + rm) and (node->val + lm1 + lm2 + rm1 + rm2)

class Solution {
public:
 int rob(TreeNode* node, int& lm, int& rm) {
    if (!node)  return 0;
    int lm1 = 0, lm2 = 0, rm1 = 0, rm2 = 0;

    lm = rob(node->left, lm1, rm1);
    rm = rob(node->right, lm2, rm2);

    return max(node->val + lm1 + rm1 + lm2 + rm2, lm + rm);
  }

 int rob(TreeNode* root) {
    int res = 0;
    int lm = 0, rm = 0;
    res = rob(root, lm, rm);
    return res;
 }
};

351 Android Unlock Patterns

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern: Each pattern must connect at least m keys and at most n keys. All the keys must be distinct. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed. The order of keys used matters.

Explanation:

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |

Invalid move: 4 - 1 - 3 - 6 Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2 Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6 Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2 Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

Example: Given m = 1, n = 1, return 9.

class Solution {
public:
    int numberOfPatterns(int m, int n) {
        int res = 0;
        vector<vector<bool>> visited(3, vector<bool>(3, false));

        // for (int i = 0; i < 3; ++i) {
        //     for (int j = 0; j < 3; ++j) {
        //         dfs(i, j, visited, res, m, n, 1);
        //     }
        // }

        int cur_res = 0;
        dfs(0, 0, visited, cur_res, m, n, 1);
        res += cur_res * 4;
        cur_res = 0;
        dfs(0, 1, visited, cur_res, m, n, 1);
        res += cur_res * 4;
        cur_res = 0;
        dfs(1, 1, visited, cur_res, m, n, 1);
        res += cur_res;

        return res;
    }

    void dfs(int x, int y, vector<vector<bool>>& visited, int &cnt, int m, int n, int level) {
        if (level >= m && level <= n) cnt++;
        if (level > n) return;
        visited[x][y] = true;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (x == i && j == y || visited[i][j]) continue;
                if (isValidMove(x, y, i, j, visited)) {
                    dfs(i, j, visited, cnt, m, n, level + 1);
                }
            }
        }
        visited[x][y] = false;
    }

    bool isValidMove(int x, int y, int i, int j, vector<vector<bool>>& visited) {
        if (visited[i][j]) return false;
        int col_diff = abs(y - j);
        int row_diff = abs(x - i);
        if (col_diff == 2) {
            if (row_diff == 2) return visited[1][1];
            else if (row_diff == 0) return visited[x][1];
        } else if (col_diff == 0) {
            if (row_diff == 2) return visited[1][y];
        }

        return true;
    }
};

386. Lexicographical Numbers

Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res;
        for (int i = 1; i < 10; ++i) dfs(i, res, n);
        return res;
    }

    void dfs(int a, vector<int>& res, int n) {
        if (a <= n) {
            res.push_back(a);
            for (int i = 0; i < 10; ++i) dfs(a*10+i, res, n);
        }
    }
};

399. Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:

Given a / b = 2.0, b / c = 3.0. 
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . 
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector> equations, vector& values, vector> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

class Solution {
public:
    struct Vertex {
        string a;
        double w;
        Vertex() = default;
        Vertex(string& a_, double w_) : a(a_), w(w_) {}
    };

    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> query) {
        unordered_map<string, vector<Vertex>> graph;
        for (int i = 0; i < equations.size(); ++i) {
            auto a = equations[i].first;
            auto b = equations[i].second;
            auto w = values[i];
            graph[a].emplace_back(b, w);
            graph[b].emplace_back(a, 1.0/w);
        }
        vector<double> res;
        for (auto& q : query) {
            double w = -1.0;
            unordered_set<string> visited;
            dfs(graph, q.first, q.second, 1.0, w, visited);
            res.push_back(w);
        }

        return res;
    }

    void dfs(unordered_map<string, vector<Vertex>>& graph, 
     string& start,  string& to, double w, double &res,
    unordered_set<string>& visited) {
        if (graph.find(start) == graph.end() || graph.find(to) == graph.end()) return;
        visited.emplace(start);
        if (start == to) {
            res = w;
        }
        for (auto& vertex : graph[start]) {
            if (visited.find(vertex.a) == visited.end()) {
                dfs(graph, vertex.a, to, w* vertex.w, res, visited);
            }
        }
    }
};

Maximum Length of the Loop

Given an array Indexes 0 1 2 3 4 Values 3 2 1 4 0 Values are the next index of the jump 0 -> 3 -> 4 -> 0... 1 -> 2 -> 1... Write a function to detect if there are loops. If yes, get the max length of the loop possible, otherwise just return zero.

G家题，实际上就是有向图找最大环。POJ有类似题。用一个DFS走一遍就好，用两个数组，一个记录visited，一个记录走过的长度。

int max_length(const vector<int>& arr) {
    int ret = 0;
    vector<bool> visited(arr.size(), false);
    vector<int> length(arr.size(), 0);

    function<void(int,int)> dfs = [&] (int id, int len) {
        if(visited[id]) {
            ret = std::max(ret, len - length[id]);
            return;
        }        
        visited[id] = true;
        length[id] = len;
        dfs(arr[id], len + 1);
    };

    for(int i = 0; i < arr.size(); ++i) dfs(i,0);
    return ret >= 2 ? ret : 0;
}