Teaching Kids Programming: Videos on Data Structures and Algorithms
Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Check Same Binary Tree via Recursive DFS Algorithm
To compare two binary trees, we check their values, and recursive checking left and right sub trees. If two nodes are empty, they are equal, and if one of them is none, the result is not equal.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if p is None and q is None: return True if p is None or q is None: return False if p.val != q.val: return False return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) |
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p is None and q is None:
return True
if p is None or q is None:
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)Time complexity is O(N) and space complexity is O(N) where N is the number of the nodes in the binary tree. N is the less number of nodes in the two binary tree.
Same Binary Tree Check Algorithm:
- How to Check If Two Binary Trees are the Same?
- Teaching Kids Programming – Recursive Depth First Search Algorithm to Check If Two Binary Trees are Same
- GoLang: Check Same Binary Trees via DFS or BFS Algorithms
- Teaching Kids Programming – Breadth First Search Algorithm to Check If Two Binary Trees are Same
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
471 wordsloading...
Last Post: Full Permutation Algorithm Implementation in BASH
Next Post: GoLang: Check Same Binary Trees via DFS or BFS Algorithms
