Skip to main content

Leetcode 572. Subtree of Another Tree. Python (Recursive)

572Subtree of Another Tree


Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

 

Example :

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true


SOLUTION:

class Solution:
    def isSubtree(self, r: Optional[TreeNode], sr: Optional[TreeNode]) -> bool:
        if not sr: return True
        if not r: return False
        
        if self.sameTree(r,sr):
            return True
        
        return (self.isSubtree(r.left, sr) or
        self.isSubtree(r.right, sr))
    
    def sameTree(self, r, sr):
        if not r and not sr:
            return True
        if r and sr and r.val == sr.val:
            return (self.sameTree(r.left, sr.left) and
            self.sameTree(r.right, sr.right))
        return False


Explaination :









Comments

Popular posts from this blog

Leetcode 371. Sum of Two Integers. C++ / Java

371 .  Sum of Two Integers   Given two integers  a  and  b , return  the sum of the two integers without using the operators   +   and   - .   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: -1000 <= a, b <= 1000 Solution :  C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java :  class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Leetcode 217. Contains Duplicate. Python (Easiest Approach ✅)

217 .  Contains Duplicate   Given an integer array  nums , return  true  if any value appears  at least twice  in the array, and return  false  if every element is distinct.   Example 1: Input: nums = [1,2,3,1] Output: true Example 2: Input: nums = [1,2,3,4] Output: false Example 3: Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true   Constraints: 1 <= nums.length <= 10 5 -10 9  <= nums[i] <= 10 9 class Solution: def containsDuplicate(self, nums: List[int]) -> bool: hs = set() for n in nums: if n in hs: return True hs.add(n) return False Explaination :

Number of Connected Components in an Undirected Graph (Python)

66.  Number of Connected Components in an Undirected Graph Question Link :  check here Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example 1:      0          3      |          |      1 --- 2    4 Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2. Example 2:      0           4      |           |      1 --- 2 --- 3 Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1. Note: You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges. Solution : class Solution: def counComponents(self, n: int, edges : List[List[int]]) -> i...