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

Commitc76747b

Browse files
authored
Merge pull requestneetcode-gh#1067 from ritesh-dt/main
Add solution for 199 - Binary Tree Right Side View and 66 - Plus One in C
2 parentsc159346 +4c77667 commitc76747b

File tree

2 files changed

+101
-0
lines changed

2 files changed

+101
-0
lines changed

‎c/199-Binary-Tree-Right-Side-View.c

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/*
2+
Given a binary tree, return the right side view of it (the nodes which can
3+
be seen in front when looking from the right).
4+
Ex. 1 <-
5+
/ \
6+
2 3 <- -> [1, 3, 4]
7+
\ \
8+
5 4 <-
9+
10+
11+
The right side view is basically the last element at each level of the tree.
12+
So BFS is one way this problem can be solved.
13+
14+
The solution below uses recursion, where on reaching a new depth we add that
15+
node as the right view for that depth. We recursively visit the right child
16+
before the left child to get the right view.
17+
18+
Time: O(n)
19+
Space: O(n)
20+
*/
21+
22+
/**
23+
* Definition for a binary tree node.
24+
* struct TreeNode {
25+
* int val;
26+
* struct TreeNode *left;
27+
* struct TreeNode *right;
28+
* };
29+
*/
30+
31+
voiddfs(structTreeNode*root,int*result,int*returnSize,intdepth) {
32+
if (root==NULL)
33+
return;
34+
35+
// If a new depth is reached, add the node as right view for that depth
36+
if (*returnSize <=depth) {
37+
*returnSize+=1;
38+
result[depth]=root->val;
39+
}
40+
41+
// Visit the right child first then left child
42+
dfs(root->right,result,returnSize,depth+1);
43+
dfs(root->left,result,returnSize,depth+1);
44+
}
45+
46+
/**
47+
* Note: The returned array must be malloced, assume caller calls free().
48+
*/
49+
int*rightSideView(structTreeNode*root,int*returnSize) {
50+
// Size of result array depends on the depth of tree, which can be precomputed
51+
int*result= (int*)malloc(sizeof(int)*100);
52+
*returnSize=0;
53+
54+
dfs(root,result,returnSize,0);
55+
56+
returnresult;
57+
}

‎c/66-Plus-One.c

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
/*
2+
Given an integer array where the elements represent the digits of a number,
3+
return the resulting array when we add one to it.
4+
Ex. digits = [1,2,3] + 1 -> [1,2,4]
5+
6+
The length of the array after adding 1 will either remain the same or
7+
increase by 1. So we keep the size of the result array as n+1 during the
8+
start. We iterate from the last digit to the first digit backwards and
9+
keep track of the carry generated by the previous digit.
10+
11+
If there is a carry left at the end, the addition caused the length to
12+
increase, so we return the result. Else if there is no carry, the length
13+
remained constant, so we skip the first element of result and return.
14+
15+
Time: O(n)
16+
Space: O(n)
17+
*/
18+
19+
/**
20+
* Note: The returned array must be malloced, assume caller calls free().
21+
*/
22+
int*plusOne(int*digits,intdigitsSize,int*returnSize){
23+
24+
// Reserve the result with a digitsSize+1 size array
25+
int*result= (int*)malloc(sizeof(int)*(digitsSize+1));
26+
*returnSize=digitsSize+1;
27+
result[0]=1;
28+
29+
intcarry=1;
30+
for (inti=digitsSize;i>0;--i) {
31+
intsum=digits[i-1]+carry;
32+
carry=sum/10;
33+
sum=sum%10;
34+
35+
result[i]=sum;
36+
}
37+
38+
if (carry)
39+
returnresult;
40+
41+
// Skip the additional element which was reserved for carry
42+
*returnSize=digitsSize;
43+
returnresult+1;
44+
}

0 commit comments

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