Skip to content

Commit 6a3e3fd

Browse files
ThanhNITThanhNIT
authored
Added tasks 84-101
1 parent bbe5057 commit 6a3e3fd

File tree

15 files changed

+442
-0
lines changed

15 files changed

+442
-0
lines changed

‎LeetCodeNet.Tests/G0001_0100/S0084_largest_rectangle_in_histogram/SolutionTest.cs

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
namespace LeetCodeNet.G0001_0100.S0084_largest_rectangle_in_histogram {
2+
3+
using Xunit;
4+
5+
public class SolutionTest {
6+
[Fact]
7+
public void LargestRectangleArea() {
8+
Assert.Equal(10, new Solution().LargestRectangleArea(new int[] { 2, 1, 5, 6, 2, 3 }));
9+
}
10+
11+
[Fact]
12+
public void LargestRectangleArea2() {
13+
Assert.Equal(4, new Solution().LargestRectangleArea(new int[] { 2, 4 }));
14+
}
15+
}
16+
}

‎LeetCodeNet.Tests/G0001_0100/S0094_binary_tree_inorder_traversal/SolutionTest.cs

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
namespace LeetCodeNet.G0001_0100.S0094_binary_tree_inorder_traversal {
2+
3+
using Xunit;
4+
using LeetCodeNet.Com_github_leetcode;
5+
6+
public class SolutionTest {
7+
[Fact]
8+
public void InorderTraversal() {
9+
TreeNode treeNode = new TreeNode(1);
10+
TreeNode treeNode2 = new TreeNode(2);
11+
treeNode.right = treeNode2;
12+
treeNode2.left = new TreeNode(3);
13+
Assert.Equal(new List<int> { 1, 3, 2 }, new Solution().InorderTraversal(treeNode));
14+
}
15+
16+
[Fact]
17+
public void InorderTraversal2() {
18+
Assert.Equal(new List<int> { }, new Solution().InorderTraversal(null));
19+
}
20+
21+
[Fact]
22+
public void InorderTraversal3() {
23+
Assert.Equal(new List<int> { 1 }, new Solution().InorderTraversal(new TreeNode(1)));
24+
}
25+
}
26+
}

‎LeetCodeNet.Tests/G0001_0100/S0096_unique_binary_search_trees/SolutionTest.cs

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
namespace LeetCodeNet.G0001_0100.S0096_unique_binary_search_trees {
2+
3+
using Xunit;
4+
5+
public class SolutionTest {
6+
[Fact]
7+
public void NumTrees() {
8+
Assert.Equal(5, new Solution().NumTrees(3));
9+
}
10+
11+
[Fact]
12+
public void NumTrees2() {
13+
Assert.Equal(1, new Solution().NumTrees(1));
14+
}
15+
}
16+
}

‎LeetCodeNet.Tests/G0001_0100/S0098_validate_binary_search_tree/SolutionTest.cs

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
namespace LeetCodeNet.G0001_0100.S0098_validate_binary_search_tree {
2+
3+
using Xunit;
4+
using LeetCodeNet.Com_github_leetcode;
5+
6+
public class SolutionTest {
7+
[Fact]
8+
public void IsValidBST() {
9+
TreeNode treeNode = new TreeNode(2);
10+
treeNode.left = new TreeNode(1);
11+
treeNode.right = new TreeNode(3);
12+
Assert.True(new Solution().IsValidBST(treeNode));
13+
}
14+
15+
[Fact]
16+
public void IsValidBST2() {
17+
TreeNode treeNode = new TreeNode(5);
18+
treeNode.left = new TreeNode(1);
19+
TreeNode treeNode2 = new TreeNode(4);
20+
treeNode2.left = new TreeNode(3);
21+
treeNode2.right = new TreeNode(6);
22+
treeNode.right = treeNode2;
23+
Assert.False(new Solution().IsValidBST(treeNode));
24+
}
25+
}
26+
}

‎LeetCodeNet.Tests/G0101_0200/S0101_symmetric_tree/SolutionTest.cs

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
namespace LeetCodeNet.G0101_0200.S0101_symmetric_tree {
2+
3+
using Xunit;
4+
using LeetCodeNet.Com_github_leetcode;
5+
6+
public class SolutionTest {
7+
[Fact]
8+
public void IsSymmetric() {
9+
TreeNode treeNode = new TreeNode(1);
10+
treeNode.left = new TreeNode(2);
11+
treeNode.right = new TreeNode(2);
12+
treeNode.left.left = new TreeNode(3);
13+
treeNode.left.right = new TreeNode(4);
14+
treeNode.right.left = new TreeNode(4);
15+
treeNode.right.right = new TreeNode(3);
16+
Assert.True(new Solution().IsSymmetric(treeNode));
17+
}
18+
19+
[Fact]
20+
public void IsSymmetric2() {
21+
TreeNode treeNode = new TreeNode(1);
22+
treeNode.left = new TreeNode(2);
23+
treeNode.right = new TreeNode(2);
24+
treeNode.left.right = new TreeNode(3);
25+
treeNode.right.right = new TreeNode(3);
26+
Assert.False(new Solution().IsSymmetric(treeNode));
27+
}
28+
}
29+
}

‎LeetCodeNet/G0001_0100/S0084_largest_rectangle_in_histogram/Solution.cs

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
namespace LeetCodeNet.G0001_0100.S0084_largest_rectangle_in_histogram {
2+
3+
// #Hard #Top_100_Liked_Questions #Top_Interview_Questions #Array #Stack #Monotonic_Stack
4+
// #Big_O_Time_O(n_log_n)_Space_O(log_n) #2024_01_08_Time_304_ms_(30.92%)_Space_52.4_MB_(29.92%)
5+
6+
public class Solution {
7+
public int LargestRectangleArea(int[] heights) {
8+
int maxArea = 0, i = 0;
9+
Stack<int> stack = new Stack<int>();
10+
while (i <= heights.Length) {
11+
var currHeight = i == heights.Length ? 0 : heights[i];
12+
if (!stack.Any() || currHeight >= heights[stack.Peek()]) {
13+
stack.Push(i);
14+
i++;
15+
}
16+
else {
17+
int index = stack.Pop();
18+
int height = heights[index];
19+
int width = (!stack.Any()) ? i : (i - 1) - stack.Peek();
20+
maxArea = Math.Max(maxArea, height * width);
21+
}
22+
}
23+
return maxArea;
24+
}
25+
}
26+
}

‎LeetCodeNet/G0001_0100/S0084_largest_rectangle_in_histogram/readme.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
84\. Largest Rectangle in Histogram
2+
3+
Hard
4+
5+
Given an array of integers `heights` representing the histogram's bar height where the width of each bar is `1`, return _the area of the largest rectangle in the histogram_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg)
10+
11+
**Input:** heights = [2,1,5,6,2,3]
12+
13+
**Output:** 10
14+
15+
**Explanation:** The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
16+
17+
**Example 2:**
18+
19+
![](https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg)
20+
21+
**Input:** heights = [2,4]
22+
23+
**Output:** 4
24+
25+
**Constraints:**
26+
27+
* <code>1 <= heights.length <= 10<sup>5</sup></code>
28+
* <code>0 <= heights[i] <= 10<sup>4</sup></code>

‎LeetCodeNet/G0001_0100/S0094_binary_tree_inorder_traversal/Solution.cs

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
namespace LeetCodeNet.G0001_0100.S0094_binary_tree_inorder_traversal {
2+
3+
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search #Tree #Binary_Tree
4+
// #Stack #Data_Structure_I_Day_10_Tree #Udemy_Tree_Stack_Queue #Big_O_Time_O(n)_Space_O(n)
5+
// #2024_01_08_Time_90_ms_(99.30%)_Space_45.5_MB_(6.37%)
6+
7+
using LeetCodeNet.Com_github_leetcode;
8+
9+
/**
10+
* Definition for a binary tree node.
11+
* public class TreeNode {
12+
* public int val;
13+
* public TreeNode left;
14+
* public TreeNode right;
15+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
16+
* this.val = val;
17+
* this.left = left;
18+
* this.right = right;
19+
* }
20+
* }
21+
*/
22+
public class Solution {
23+
public IList<int> InorderTraversal(TreeNode root) {
24+
if (root == null) {
25+
return new List<int>();
26+
}
27+
var answer = new List<int>();
28+
InorderTraversal(root, answer);
29+
return answer;
30+
}
31+
32+
private void InorderTraversal(TreeNode root, IList<int> answer) {
33+
if (root == null) {
34+
return;
35+
}
36+
if (root.left != null) {
37+
InorderTraversal(root.left, answer);
38+
}
39+
answer.Add((int)root.val);
40+
if (root.right != null) {
41+
InorderTraversal(root.right, answer);
42+
}
43+
}
44+
}
45+
}

‎LeetCodeNet/G0001_0100/S0094_binary_tree_inorder_traversal/readme.md

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
94\. Binary Tree Inorder Traversal
2+
3+
Easy
4+
5+
Given the `root` of a binary tree, return _the inorder traversal of its nodes' values_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg)
10+
11+
**Input:** root = [1,null,2,3]
12+
13+
**Output:** [1,3,2]
14+
15+
**Example 2:**
16+
17+
**Input:** root = []
18+
19+
**Output:** []
20+
21+
**Example 3:**
22+
23+
**Input:** root = [1]
24+
25+
**Output:** [1]
26+
27+
**Example 4:**
28+
29+
![](https://assets.leetcode.com/uploads/2020/09/15/inorder_5.jpg)
30+
31+
**Input:** root = [1,2]
32+
33+
**Output:** [2,1]
34+
35+
**Example 5:**
36+
37+
![](https://assets.leetcode.com/uploads/2020/09/15/inorder_4.jpg)
38+
39+
**Input:** root = [1,null,2]
40+
41+
**Output:** [1,2]
42+
43+
**Constraints:**
44+
45+
* The number of nodes in the tree is in the range `[0, 100]`.
46+
* `-100 <= Node.val <= 100`
47+
48+
**Follow up:** Recursive solution is trivial, could you do it iteratively?

‎LeetCodeNet/G0001_0100/S0096_unique_binary_search_trees/Solution.cs

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
namespace LeetCodeNet.G0001_0100.S0096_unique_binary_search_trees {
2+
3+
// #Medium #Top_100_Liked_Questions #Dynamic_Programming #Math #Tree #Binary_Tree
4+
// #Binary_Search_Tree #Dynamic_Programming_I_Day_11 #Big_O_Time_O(n)_Space_O(1)
5+
// #2024_01_08_Time_13_ms_(98.48%)_Space_26.2_MB_(88.64%)
6+
7+
public class Solution {
8+
public int NumTrees(int n) {
9+
long result = 1;
10+
for (int i = 0; i < n; i++) {
11+
result *= 2L * n - i;
12+
result /= i + 1;
13+
}
14+
result /= n + 1;
15+
return (int) result;
16+
}
17+
}
18+
}

‎LeetCodeNet/G0001_0100/S0096_unique_binary_search_trees/readme.md

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
96\. Unique Binary Search Trees
2+
3+
Medium
4+
5+
Given an integer `n`, return _the number of structurally unique **BST'**s (binary search trees) which has exactly_ `n` _nodes of unique values from_ `1` _to_ `n`.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg)
10+
11+
**Input:** n = 3
12+
13+
**Output:** 5
14+
15+
**Example 2:**
16+
17+
**Input:** n = 1
18+
19+
**Output:** 1
20+
21+
**Constraints:**
22+
23+
* `1 <= n <= 19`

‎LeetCodeNet/G0001_0100/S0098_validate_binary_search_tree/Solution.cs

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
namespace LeetCodeNet.G0001_0100.S0098_validate_binary_search_tree {
2+
3+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search #Tree #Binary_Tree
4+
// #Binary_Search_Tree #Data_Structure_I_Day_14_Tree #Level_1_Day_8_Binary_Search_Tree
5+
// #Udemy_Tree_Stack_Queue #Big_O_Time_O(N)_Space_O(log(N))
6+
// #2024_01_08_Time_75_ms_(97.31%)_Space_45.3_MB_(19.73%)
7+
8+
using LeetCodeNet.Com_github_leetcode;
9+
10+
/**
11+
* Definition for a binary tree node.
12+
* public class TreeNode {
13+
* public int val;
14+
* public TreeNode left;
15+
* public TreeNode right;
16+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
public class Solution {
24+
public bool IsValidBST(TreeNode root) {
25+
return Solve(root, long.MinValue, long.MaxValue);
26+
}
27+
// we will send a valid range and check whether the root lies in the range
28+
// and update the range for the subtrees
29+
private bool Solve(TreeNode root, long left, long right) {
30+
if (root == null) {
31+
return true;
32+
}
33+
if (root.val <= left || root.val >= right) {
34+
return false;
35+
}
36+
return Solve(root.left, left, (long)root.val) && Solve(root.right, (long)root.val, right);
37+
}
38+
}
39+
}

‎LeetCodeNet/G0001_0100/S0098_validate_binary_search_tree/readme.md

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
98\. Validate Binary Search Tree
2+
3+
Medium
4+
5+
Given the `root` of a binary tree, _determine if it is a valid binary search tree (BST)_.
6+
7+
A **valid BST** is defined as follows:
8+
9+
* The left subtree of a node contains only nodes with keys **less than** the node's key.
10+
* The right subtree of a node contains only nodes with keys **greater than** the node's key.
11+
* Both the left and right subtrees must also be binary search trees.
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg)
16+
17+
**Input:** root = [2,1,3]
18+
19+
**Output:** true
20+
21+
**Example 2:**
22+
23+
![](https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg)
24+
25+
**Input:** root = [5,1,4,null,null,3,6]
26+
27+
**Output:** false
28+
29+
**Explanation:** The root node's value is 5 but its right child's value is 4.
30+
31+
**Constraints:**
32+
33+
* The number of nodes in the tree is in the range <code>[1, 10<sup>4</sup>]</code>.
34+
* <code>-2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1</code>

0 commit comments

Comments
 (0)