LeetCode ๐๏ธ/Tree
LeetCode ๐๏ธ/Tree
211. Design Add and Search Words Data Structure
Description: Solution: For solving this problem, we use TrieNode (prefix tree). In serach(), we use recursion method to check "." if c is "." we are gonna check the values next to the "." We put the values in dfs() from the next one, so that check recursively by increasing i.
LeetCode ๐๏ธ/Tree
235. Lowest Common Ancestor of a Binary Search Tree
Description: Solution: Start from root. If both p, q is less than root, we are gonna see the left portion of root. elif both p, q is more than root, we are gonna see the right portion of root. Other cases have a root as a LCA node in the Tree. Time Complextiy: O(logn) Space Complexity: O(1)
LeetCode ๐๏ธ/Tree
230. Kth Smallest Element in a BST
Description: Solution: First, we keep going left in tree. We put the values in stack. Pop the value from the stack. => From most smallest value. Everytime we pop, increase n to check if there is kth smallest value. If it doensn't exist, now we can go right at current node to see the next.
LeetCode ๐๏ธ/Tree
297. Serialize and Deserialize Binary Tree
Description: Solution: serialize() if node is None --> append('n') if node exist --> append(str(node.val)) We should search from left! ','.join(res) => ['a', 'b', 'c'] --> "a,b,c" deserialize() data.split(",") => "a,b,c" --> ['a', 'b', 'c'] self.i is the global variable 'n' means null, so return null. Don't forgetself.i += 1 We are gonna append TreeNode object. '(val)' is the string form, so we ..
LeetCode ๐๏ธ/Tree
98. Validate Binary Search Tree
Description: Solution: In helper(), we are gonna update the boundary to check the val is satisfied in boundary condition. min_val is the left boundary. max_val is the right boundary. helper() return the new boundary. "-2**31-1" and "2**31" are the initial value for the root value. It represents "-∞
LeetCode ๐๏ธ/Tree
105. Construct Binary Tree from Preorder and Inorder Traversal
Description: Solution: In the recursion, we set the root and mid, and then divide two portion: right & left. root is always the first value of preorder[] mid is always the index of root of inorder[] left portion: preorder[1: mid+1] and inorder[:mid]. right portion: preorder[mid+1:] and inorder[mid+1:].
LeetCode ๐๏ธ/Tree
572. Subtree of Another Tree
Description: This question is to know whether subRoot is in root or not. If the subRoot is in the root, return True. However, in example 2, it returns False because subRoot has unexpected child node. This Question set it is false like example 2. Solution(Recursion with DFS): Before looking at identical function, we should look the cases. In the first case, we return true when we don't have subRo..
LeetCode ๐๏ธ/Tree
102. Binary Tree Level Order Traversal
Description: This question asked us to get 2 dimensional array which includes the value and level of tree. "3" is the only value of first level of tree. 9, 20 are the second level. 15, 7 are the third level. Each level is in the same list, we can see the different list in the output list. Solution: First, the solution used the queue method in collections library. "res" is what we are gonna retur..
LeetCode ๐๏ธ/Tree
124. Binary Tree Maximum Path
This is the Leetcode question called "Binary Tree Maximum Path): Every nodes have a specific value. Some are positive and some are negative. We can start from any node of tree. When we start, we can make a direction to other node. Solution: First, we make the list name "res" to return the sum. The function "dfs" is used for recurssion and return the value of the maximum case when we go thorugh t..
