0111-0120

111. Minimum Depth of Binary Tree $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int minDepth(TreeNode* root) {
    if (!root) return 0;

    int ans = 0;

    queue<TreeNode*> queue;
    queue.push(root);

    while (!queue.empty()) {
      ++ans;
      for (int i = queue.size(); i > 0; --i) {
        TreeNode* node = queue.front();
        queue.pop();
        if (!node->left && !node->right) return ans;
        if (node->left) queue.push(node->left);
        if (node->right) queue.push(node->right);
      }
    }

    return -1;
  }
};

112. Path Sum $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
 public:
  bool hasPathSum(TreeNode* root, int sum) {
    if (!root) return false;
    if (root->val == sum && !root->left && !root->right) return true;

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

113. Path Sum II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  vector<vector<int>> pathSum(TreeNode* root, int sum) {
    vector<vector<int>> ans;
    vector<int> path;

    dfs(root, sum, path, ans);

    return ans;
  }

 private:
  void dfs(TreeNode* root, int sum, vector<int>& path,
           vector<vector<int>>& ans) {
    if (!root) return;
    if (sum == root->val && !root->left && !root->right) {
      path.push_back(root->val);
      ans.push_back(path);
      path.pop_back();
      return;
    }

    path.push_back(root->val);
    dfs(root->left, sum - root->val, path, ans);
    dfs(root->right, sum - root->val, path, ans);
    path.pop_back();
  }
};

114. Flatten Binary Tree to Linked List $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  void flatten(TreeNode* root) {
    if (!root) return;

    flatten(root->right);
    flatten(root->left);
    root->right = next;
    root->left = NULL;
    next = root;
  }

 private:
  TreeNode* next = NULL;
};

115. Distinct Subsequences $\star\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int numDistinct(string s, string t) {
    const int m = s.length();
    const int n = t.length();

    vector<vector<long>> dp(m + 1, vector<long>(n + 1));

    for (int i = 0; i <= m; ++i)
      for (int j = 0; j <= n; ++j) {
        if (j == 0)
          dp[i][j] = 1;
        else if (i == 0)
          dp[i][j] = 0;
        else
          dp[i][j] =
              dp[i - 1][j] + (s[i - 1] == t[j - 1] ? dp[i - 1][j - 1] : 0);
      }

    return dp[m][n];
  }
};

116. Populating Next Right Pointers in Each Node $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  Node* connect(Node* root) {
    Node* node = root;

    while (node && node->left) {
      Node* next = node->left;
      while (node) {
        node->left->next = node->right;
        node->right->next = node->next ? node->next->left : NULL;
        node = node->next;
      }
      node = next;
    }

    return root;
  }
};

117. Populating Next Right Pointers in Each Node II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  Node* connect(Node* root) {
    Node* node = root;
    Node* curr = new Node(NULL);
    Node* prev = curr;

    while (node) {
      while (node) {
        curr->next = node->left;
        if (curr->next) curr = curr->next;
        curr->next = node->right;
        if (curr->next) curr = curr->next;
        node = node->next;
      }
      node = prev->next;
      curr = prev;
    }

    return root;
  }
};

118. Pascal's Triangle $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  vector<vector<int>> generate(int numRows) {
    vector<vector<int>> ans;

    for (int i = 0; i < numRows; ++i) ans.push_back(vector<int>(i + 1, 1));

    for (int i = 2; i < numRows; ++i)
      for (int j = 1; j < ans[i].size() - 1; ++j)
        ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];

    return ans;
  }
};

119. Pascal's Triangle II $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  vector<int> getRow(int rowIndex) {
    vector<int> ans(rowIndex + 1, 1);

    for (int i = 2; i < rowIndex + 1; ++i)
      for (int j = 1; j < i; ++j) ans[i - j] += ans[i - j - 1];

    return ans;
  }
};

120. Triangle $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
 public:
  int minimumTotal(vector<vector<int>>& triangle) {
    for (int i = triangle.size() - 2; i >= 0; --i)
      for (int j = 0; j <= i; ++j)
        triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);

    return triangle[0][0];
  }
};