Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitac2ef79

Browse files
authored
Batch-3/Neetcode-150/Added hints (neetcode-gh#3745)
1 parent7a6051c commitac2ef79

11 files changed

+343
-1
lines changed

‎articles/subtree-of-a-binary-tree.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
##1.Brute Force (DFS)
1+
##1.Depth First Search (DFS)
22

33
::tabs-start
44

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of nodes.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
You can observe that the in-order traversal helps divide the array into two halves based on the root node: the left part corresponds to the left subtree, and the right part corresponds to the right subtree. Can you think of how we can get the index of the root node in the in-order array? Maybe you should look into the pre-order traversal array.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
From the pre-order traversal, we know that the first node is the root node. Using this information, can you now construct the binary tree?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
After getting the root node from pre-order traversal, we then look for the index of that node in the in-order array. We can linearly search for the index but this would be an <code>O(n^2)</code> solution. Can you think of a better way? Maybe we can use a data structure to get the index of a node in <code>O(1)</code>?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We can use a hash map to get the index of any node in the in-order array in <code>O(1)</code> time. How can we implement this?
38+
</p>
39+
</details>
40+
41+
<br>
42+
<detailsclass="hint-accordion">
43+
<summary>Hint 5</summary>
44+
<p>
45+
We use Depth First Search (DFS) to construct the tree. A global variable tracks the current index in the pre-order array. Indices <code>l</code> and <code>r</code> represent the segment in the in-order array for the current subtree. For each node in the pre-order array, we create a node, find its index in the in-order array using the hash map, and recursively build the left and right subtrees by splitting the range <code>[l, r]</code> into two parts for the left and right subtrees.
46+
</p>
47+
</details>
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of nodes in the given tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A brute force solution would involve checking the path sum between every pair of nodes in the tree, leading to an <code>O(n^2)</code> time complexity. Can you think of a more efficient approach? Consider what information you would need at each node to calculate the path sum if it passes through the current node.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
At a node, there are three scenarios to compute the maximum path sum that includes the current node. One includes both the left and right subtrees, with the current node as the connecting node. Another path sum includes only one of the subtrees (either left or right), but not both. Another considers the path sum extending from the current node to the parent. However, the parent’s contribution is computed during the traversal at the parent node. Can you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can use the Depth First Search (DFS) algorithm to traverse the tree. We maintain a global variable to track the maximum path sum. At each node, we first calculate the maximum path sum from the left and right subtrees by traversing them. After that, we compute the maximum path sum at the current node. This approach follows a post-order traversal, where we visit the subtrees before processing the current node.
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We return the maximum path sum from the current node to its parent, considering only one of the subtrees (either left or right) to extend the path. While calculating the left and right subtree path sums, we also ensure that we take the maximum with <code>0</code> to avoid negative sums, indicating that we should not include the subtree path in the calculation of the maximum path at the current node.
38+
</p>
39+
</details>
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of nodes in the given tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
In the right-side view of a tree, can you identify the nodes that are visible? Maybe you could traverse the tree level by level and determine which nodes are visible from the right side.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
The nodes visible in the right-side view are the last nodes at each level of the tree. Can you think of an algorithm to identify these nodes? Maybe an algorithm that can traverse the tree level by level.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can use the Breadth First Search (BFS) algorithm to traverse the tree level by level. Once we completely visit a level, we take the last node of that level and add it to the result array. After processing all levels, we return the result.
30+
</p>
31+
</details>
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n)</code> time and<code>O(n)</code> space, where <code>n</code> is the number of nodes in the given tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A brute force solution would involve considering every node and checking if the path from the root to that node is valid, resulting in an <code>O(n^2)</code> time complexity. Can you think of a better approach?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the Depth First Search (DFS) algorithm to traverse the tree. But can you think of a way to determine if the current node is a good node in a single traversal? Maybe we need to track a value while traversing the tree.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
While traversing the tree, we should track the maximum value along the current path. This allows us to determine whether the nodes we encounter are good. We can use a global variable to count the number of good nodes.
30+
</p>
31+
</details>
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution as good or better than <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of nodes in the given tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A naive solution would be to store the node values in an array, sort it, and then return the <code>k-th</code> value from the sorted array. This would be an <code>O(nlogn)</code> solution due to sorting. Can you think of a better way? Maybe you should try one of the traversal technique.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the Depth First Search (DFS) algorithm to traverse the tree. Since the tree is a Binary Search Tree (BST), we can leverage its structure and perform an in-order traversal, where we first visit the left subtree, then the current node, and finally the right subtree. Why? Because we need the <code>k-th</code> smallest integer, and by visiting the left subtree first, we ensure that we encounter smaller nodes before the current node. How can you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We keep a counter variable <code>cnt</code> to track the position of the current node in the ascending order of values. When <code>cnt == k</code>, we store the current node's value in a global variable and return. This allows us to identify and return the <code>k-th</code> smallest element during the in-order traversal.
30+
</p>
31+
</details>
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of nodes in the given tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
The level of a tree refers to the nodes that are at equal distance from the root node. Can you think of an algorithm that traverses the tree level by level, rather than going deeper into the tree?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use the Breadth First Search (BFS) algorithm to traverse the tree level by level. BFS uses a queue data structure to achieve this. At each step of BFS, we only iterate over the queue up to its size at that step. Then, we take the left and right child pointers and add them to the queue. This allows us to explore all paths simultaneously.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
The number of times we iterate the queue corresponds to the number of levels in the tree. At each step, we pop all nodes from the queue for the current level and add them collectively to the resultant array. This ensures that we capture all nodes at each level of the tree.
30+
</p>
31+
</details>
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution as good or better than <code>O(h)</code> time and <code>O(h)</code> space, where <code>h</code> is the height of the given tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A Binary Search Tree (BST) is a tree in which the values of all nodes in the left subtree of a node are less than the node's value, and the values of all nodes in the right subtree are greater than the node's value. Additionally, every subtree of a BST must also satisfy this property, meaning the "less than" or "greater than" condition is valid for all nodes in the tree, not just the root. How can you use this idea to find the LCA of the given nodes in the tree?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use recursion to traverse the tree. Can you figure out the conditions we encounter when choosing a path between the left and right subtrees during traversal using the values of the two given nodes? Perhaps you can determine the LCA by traversing based on these conditions.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
If nodes <code>p</code> and <code>q</code> are in different subtrees, a split occurs, making the current node the LCA. If both are in the left or right subtree, the LCA lies in that subtree and we further choose that subtree to traverse using recursion. You should also handle other multiple scenarios to get the LCA.
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
The LCA can also be one of the nodes, <code>p</code> or <code>q</code>, if the current node is equal to either of them. This is because if we encounter either <code>p</code> or <code>q</code> during the traversal, that node is the LCA.
38+
</p>
39+
</details>
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of nodes in the given tree.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A straightforward way to serialize a tree is by traversing it and adding nodes to a string separated by a delimiter (example: ","), but this does not handle <code>null</code> nodes effectively. During deserialization, it becomes unclear where to stop or how to handle missing children. Can you think of a way to indicate <code>null</code> nodes explicitly?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
Including a placeholder for <code>null</code> nodes (example: "N") during serialization ensures that the exact structure of the tree is preserved. This placeholder allows us to identify missing children and reconstruct the tree accurately during deserialization.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can use the Depth First Search (DFS) algorithm for both serialization and deserialization. During serialization, we traverse the tree and add node values to the result string separated by a delimiter, inserting <code>N</code> whenever we encounter a <code>null</code> node. During deserialization, we process the serialized string using an index <code>i</code>, create nodes for valid values, and return from the current path whenever we encounter <code>N</code>, reconstructing the tree accurately.
30+
</p>
31+
</details>

‎hints/subtree-of-a-binary-tree.md‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution as good or better than <code>O(m * n)</code> time and <code>O(m + n)</code> space, where <code>n</code> and <code>m</code> are the number of nodes in <code>root</code> and <code>subRoot</code>, respectively.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A subtree of a tree is a tree rooted at a specific node. We need to check whether the given <code>subRoot</code> is identical to any of the subtrees of <code>root</code>. Can you think of a recursive way to check this? Maybe you can leverage the idea of solving a problem where two trees are given, and you need to check whether they are identical in structure and values.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
When two trees are identical, it means that every node in both trees has the same value and structure. We can use the Depth First Search (DFS) algorithm to solve the problem. How do you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We traverse the given <code>root</code>, and at each node, we check if the subtree rooted at that node is identical to the given <code>subRoot</code>. We use a helper function, <code>sameTree(root1, root2)</code>, to determine whether the two trees passed to it are identical in both structure and values.
30+
</p>
31+
</details>

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp