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

Commit943dce6

Browse files
authored
Added tasks 226-238
1 parentf811f46 commit943dce6

File tree

10 files changed

+326
-0
lines changed

10 files changed

+326
-0
lines changed
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
226\. Invert Binary Tree
2+
3+
Easy
4+
5+
Given the`root` of a binary tree, invert the tree, and return_its root_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/03/14/invert1-tree.jpg)
10+
11+
**Input:** root =[4,2,7,1,3,6,9]
12+
13+
**Output:**[4,7,2,9,6,3,1]
14+
15+
**Example 2:**
16+
17+
![](https://assets.leetcode.com/uploads/2021/03/14/invert2-tree.jpg)
18+
19+
**Input:** root =[2,1,3]
20+
21+
**Output:**[2,3,1]
22+
23+
**Example 3:**
24+
25+
**Input:** root =[]
26+
27+
**Output:**[]
28+
29+
**Constraints:**
30+
31+
* The number of nodes in the tree is in the range`[0, 100]`.
32+
*`-100 <= Node.val <= 100`
Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
// #Easy #Top_100_Liked_Questions #Depth_First_Search #Breadth_First_Search #Tree #Binary_Tree
2+
// #Data_Structure_I_Day_12_Tree #Level_2_Day_6_Tree #Udemy_Tree_Stack_Queue
3+
// #Big_O_Time_O(n)_Space_O(n) #2023_10_09_Time_52_ms_(81.65%)_Space_44.2_MB_(79.49%)
4+
5+
functioninvertTree(root:TreeNode|null):TreeNode|null{
6+
if(root===null){
7+
returnnull
8+
}
9+
consttemp=root.left
10+
root.left=invertTree(root.right)
11+
root.right=invertTree(temp)
12+
returnroot
13+
}
14+
15+
export{invertTree}
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
230\. Kth Smallest Element in a BST
2+
3+
Medium
4+
5+
Given the`root` of a binary search tree, and an integer`k`, return_the_ <code>k<sup>th</sup></code>_smallest value (**1-indexed**) of all the values of the nodes in the tree_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/01/28/kthtree1.jpg)
10+
11+
**Input:** root =[3,1,4,null,2], k = 1
12+
13+
**Output:** 1
14+
15+
**Example 2:**
16+
17+
![](https://assets.leetcode.com/uploads/2021/01/28/kthtree2.jpg)
18+
19+
**Input:** root =[5,3,6,2,4,null,null,1], k = 3
20+
21+
**Output:** 3
22+
23+
**Constraints:**
24+
25+
* The number of nodes in the tree is`n`.
26+
* <code>1 <= k <= n <= 10<sup>4</sup></code>
27+
* <code>0 <= Node.val <= 10<sup>4</sup></code>
28+
29+
**Follow up:** If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search #Tree #Binary_Tree
2+
// #Binary_Search_Tree #Data_Structure_II_Day_17_Tree #Level_2_Day_9_Binary_Search_Tree
3+
// #Big_O_Time_O(n)_Space_O(n) #2023_10_09_Time_54_ms_(97.22%)_Space_47.7_MB_(99.80%)
4+
5+
/*
6+
* Definition for a binary tree node.
7+
* class TreeNode {
8+
* val: number
9+
* left: TreeNode | null
10+
* right: TreeNode | null
11+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
12+
* this.val = (val===undefined ? 0 : val)
13+
* this.left = (left===undefined ? null : left)
14+
* this.right = (right===undefined ? null : right)
15+
* }
16+
* }
17+
*/
18+
functionkthSmallest(root:TreeNode|null,k:number):number{
19+
letcur=root
20+
while(cur!==null){
21+
if(cur.left!==null){
22+
constleft=cur.left
23+
cur.left=null
24+
letrightmost=left
25+
while(rightmost.right!==null)rightmost=rightmost.right
26+
rightmost.right=cur
27+
cur=left
28+
}elseif(--k!==0){
29+
cur=cur.right
30+
}else{
31+
break
32+
}
33+
}
34+
returncur.val
35+
}
36+
37+
export{kthSmallest}
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
234\. Palindrome Linked List
2+
3+
Easy
4+
5+
Given the`head` of a singly linked list, return`true` if it is a palindrome.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg)
10+
11+
**Input:** head =[1,2,2,1]
12+
13+
**Output:** true
14+
15+
**Example 2:**
16+
17+
![](https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg)
18+
19+
**Input:** head =[1,2]
20+
21+
**Output:** false
22+
23+
**Constraints:**
24+
25+
* The number of nodes in the list is in the range <code>[1, 10<sup>5</sup>]</code>.
26+
*`0 <= Node.val <= 9`
27+
28+
**Follow up:** Could you do it in`O(n)` time and`O(1)` space?
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Two_Pointers #Stack #Linked_List
2+
// #Recursion #Level_2_Day_3_Linked_List #Udemy_Linked_List #Big_O_Time_O(n)_Space_O(1)
3+
// #2023_10_09_Time_96_ms_(95.67%)_Space_72.8_MB_(87.01%)
4+
5+
/*
6+
* Definition for singly-linked list.
7+
* class ListNode {
8+
* val: number
9+
* next: ListNode | null
10+
* constructor(val?: number, next?: ListNode | null) {
11+
* this.val = (val===undefined ? 0 : val)
12+
* this.next = (next===undefined ? null : next)
13+
* }
14+
* }
15+
*/
16+
functionisPalindrome(head:ListNode|null):boolean{
17+
if(head===null||head.next===null){
18+
// Empty list or single element is considered a palindrome.
19+
returntrue
20+
}
21+
letlen=0
22+
letright=head
23+
// Calculate the length of the list.
24+
while(right!==null){
25+
right=right.next
26+
len++
27+
}
28+
// Find the middle of the list.
29+
letmiddle=Math.floor(len/2)
30+
// Reset the right pointer to the head.
31+
right=head
32+
// Move the right pointer to the middle of the list.
33+
for(leti=0;i<middle;i++){
34+
right=right.next
35+
}
36+
// Reverse the right half of the list.
37+
letprev=null
38+
while(right!==null){
39+
constnext=right.next
40+
right.next=prev
41+
prev=right
42+
right=next
43+
}
44+
// Compare the left and right halves.
45+
for(leti=0;i<middle;i++){
46+
if(prev!==null&&head.val===prev.val){
47+
head=head.next
48+
prev=prev.next
49+
}else{
50+
returnfalse
51+
}
52+
}
53+
returntrue
54+
}
55+
56+
export{isPalindrome}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
236\. Lowest Common Ancestor of a Binary Tree
2+
3+
Medium
4+
5+
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
6+
7+
According to the[definition of LCA on Wikipedia](https://en.wikipedia.org/wiki/Lowest_common_ancestor): “The lowest common ancestor is defined between two nodes`p` and`q` as the lowest node in`T` that has both`p` and`q` as descendants (where we allow**a node to be a descendant of itself**).”
8+
9+
**Example 1:**
10+
11+
![](https://assets.leetcode.com/uploads/2018/12/14/binarytree.png)
12+
13+
**Input:** root =[3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
14+
15+
**Output:** 3
16+
17+
**Explanation:** The LCA of nodes 5 and 1 is 3.
18+
19+
**Example 2:**
20+
21+
![](https://assets.leetcode.com/uploads/2018/12/14/binarytree.png)
22+
23+
**Input:** root =[3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
24+
25+
**Output:** 5
26+
27+
**Explanation:** The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
28+
29+
**Example 3:**
30+
31+
**Input:** root =[1,2], p = 1, q = 2
32+
33+
**Output:** 1
34+
35+
**Constraints:**
36+
37+
* The number of nodes in the tree is in the range <code>[2, 10<sup>5</sup>]</code>.
38+
* <code>-10<sup>9</sup> <= Node.val <= 10<sup>9</sup></code>
39+
* All`Node.val` are**unique**.
40+
*`p != q`
41+
*`p` and`q` will exist in the tree.
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search #Tree #Binary_Tree
2+
// #Data_Structure_II_Day_18_Tree #Udemy_Tree_Stack_Queue #Big_O_Time_O(n)_Space_O(n)
3+
// #2023_10_09_Time_59_ms_(96.11%)_Space_52.8_MB_(24.18%)
4+
5+
/*
6+
* Definition for a binary tree node.
7+
* class TreeNode {
8+
* val: number
9+
* left: TreeNode | null
10+
* right: TreeNode | null
11+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
12+
* this.val = (val===undefined ? 0 : val)
13+
* this.left = (left===undefined ? null : left)
14+
* this.right = (right===undefined ? null : right)
15+
* }
16+
* }
17+
*/
18+
functionlowestCommonAncestor(root:TreeNode|null,p:TreeNode|null,q:TreeNode|null):TreeNode|null{
19+
if(root===null){
20+
returnnull
21+
}
22+
if(root.val===p.val||root.val===q.val){
23+
returnroot
24+
}
25+
constleft=lowestCommonAncestor(root.left,p,q)
26+
constright=lowestCommonAncestor(root.right,p,q)
27+
if(left!==null&&right!==null){
28+
returnroot
29+
}
30+
if(left!==null){
31+
returnleft
32+
}
33+
returnright
34+
}
35+
36+
export{lowestCommonAncestor}
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
238\. Product of Array Except Self
2+
3+
Medium
4+
5+
Given an integer array`nums`, return_an array_`answer`_such that_`answer[i]`_is equal to the product of all the elements of_`nums`_except_`nums[i]`.
6+
7+
The product of any prefix or suffix of`nums` is**guaranteed** to fit in a**32-bit** integer.
8+
9+
You must write an algorithm that runs in`O(n)` time and without using the division operation.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[1,2,3,4]
14+
15+
**Output:**[24,12,8,6]
16+
17+
**Example 2:**
18+
19+
**Input:** nums =[-1,1,0,-3,3]
20+
21+
**Output:**[0,0,9,0,0]
22+
23+
**Constraints:**
24+
25+
* <code>2 <= nums.length <= 10<sup>5</sup></code>
26+
*`-30 <= nums[i] <= 30`
27+
* The product of any prefix or suffix of`nums` is**guaranteed** to fit in a**32-bit** integer.
28+
29+
**Follow up:** Can you solve the problem in`O(1)`extra space complexity? (The output array**does not** count as extra space for space complexity analysis.)
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Prefix_Sum
2+
// #Data_Structure_II_Day_5_Array #Udemy_Arrays #Big_O_Time_O(n^2)_Space_O(n)
3+
// #2023_10_09_Time_89_ms_(64.48%)_Space_55.4_MB_(36.71%)
4+
5+
functionproductExceptSelf(nums:number[]):number[]{
6+
constn=nums.length
7+
constans:number[]=newArray(n)
8+
letproduct=1
9+
// Calculate the product of all elements to the left of each element
10+
for(leti=0;i<n;i++){
11+
ans[i]=product
12+
product*=nums[i]
13+
}
14+
product=1
15+
// Calculate the product of all elements to the right of each element
16+
for(leti=n-1;i>=0;i--){
17+
ans[i]*=product
18+
product*=nums[i]
19+
}
20+
returnans
21+
}
22+
23+
export{productExceptSelf}

0 commit comments

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