Author: devangini123
🌙 Problem Statement: Given the root of a binary tree, return the postorder traversal of its nodes’ values.. Examples: Example 1: Input: root = [1,null,2,3] Output: [3,2,1] Explanation: Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [4,6,7,5,2,9,8,3,1] Explanation: Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1] Constraints: The number of nodes in the tree is in the range [0, 100]. -100 right); ans.push_back(curr->val); }; traversal(root); return ans; } void traversal(struct TreeNode* curr, int* ans, int* returnSize) { if (!curr) return; traversal(curr->left, ans, returnSize); traversal(curr->right, ans, returnSize); ans[(*returnSize)++] = curr->val; } int* postorderTraversal(struct TreeNode*…
🌙 Problem Statement: Given the root of a binary tree, return the preorder traversal of its nodes’ values. Examples: Example 1: Input: root = [1,null,2,3] Output: [1,2,3] Explanation: Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [1,2,4,5,6,7,3,8,9] Explanation: Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1] Constraints: The number of nodes in the tree is in the range [0, 100]. -100 left, ans); traversal(curr->right, ans); } vector preorderTraversal(TreeNode* root) { vector ans; traversal(root, ans); return ans; } }; void traversal(struct TreeNode* curr, int* ans, int* idx) { if (!curr) return; ans[(*idx)++] = curr->val;…
🌙 Problem Statement: Given the root of a binary tree, return the inorder traversal of its nodes’ values.. Examples: Example 1: Input: root = [1,null,2,3] Output: [1,3,2] Explanation: Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [4,2,6,5,7,1,3,9,8] Explanation: Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1] Constraints: The number of nodes in the tree is in the range [0, 100]. -100 val); traversal(curr->right); }; traversal(root); return ans; } void traversal(struct TreeNode* curr, int* ans, int* index) { if (!curr) return; traversal(curr->left, ans, index); ans[(*index)++] = curr->val; traversal(curr->right, ans, index); } int* inorderTraversal(struct TreeNode*…
🌙 What is Tree Traversal? Tree traversal is the process of visiting each node in a tree. Traversal Technique: Pre-Order Traversal Order: Root → Left → Right [1, 2, 4, 5, 6, 7, 3, 8, 9] In-Order Traversal Order: Left → Root → Right [4, 2, 6, 5, 7, 1, 3, 9, 8] Post-Order Traversal Order: Left → Right → Root [4, 6, 7, 5, 2, 9, 8, 3, 1] Level-Order Traversal Order: Traverse Level by Level (Top to Bottom) [12, 3, 4, 5, 8, 6, 7, 9] Question Practice: Pre-Order Traversal Order: Root → Left → Right [A, B,…
🌙 Tree: Non-linear structure. Hierarchical in nature. Node: Can have zero or more children. Has only one parent (except root). Cannot have cycles: Mean node have only one parent, otherwise it will form cycle (graphs). Exactly one path exists between any two nodes. No two parents can share the same child. Why Tree Data Structures? Not every type of data can be stored in an array or linked list. When we need to store hierarchical data, we use trees. Examples: File Systems HTML DOM Databases Hierarchical Data Models Types of Trees: General Tree: Any number of children. Binary Tree: At…
Problem Statement: You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Examples: Example 1: Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max ————— —– [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6…
Problem Statement: Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise. In other words, return true if one of s1’s permutations is the substring of s2. Examples: Example 1: Input: s1 = “ab”, s2 = “eidbaooo” Output: true Explanation: s2 contains one permutation of s1 (“ba”). Example 2: Input: s1 = “ab”, s2 = “eidboaoo” Output: false Constraints: 1 len(s2): return False hashS = [0] * 26 hashW = [0] * 26 window_length = len(s1) for i in range(window_length): hashS[ord(s1[i]) – ord(‘a’)] += 1 hashW[ord(s2[i]) – ord(‘a’)] += 1 i =…
Problem Statement: You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations. Examples: Example 1: Input: s = “ABAB”, k = 2 Output: 2 Explanation: Replace the two ‘A’s with two ‘B’s or vice versa. Example 2: Input: s = “AABABBA”, k = 1 Output: 4 Explanation: Replace the one ‘A’ in the middle with…
Problem Statement: Given a string s, find the length of the longest substring without duplicate characters. Examples: Example 1: Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3. Example 2: Input: s = “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1. Example 3: Input: s = “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring. Constraints: 0
Problem Statement: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Examples: Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Example 2: Input: height = [4,2,0,3,2,5] Output:9 Constraints: n == height.length 1 =0; i–){ maxR[i] = (arr[i] > maxR[i+1]) ? arr[i] : maxR[i+1]; } int ans = 0; for(int i=0; i 0) ? waterTrapped : 0; } return ans;…
