Teaching Kids Programming: Videos on Data Structures and Algorithms
Given the root to a binary tree root, return whether it is symmetric.
Constraints
n ≤ 100,000 where n is the number of nodes in root
Recursive Algorithm to Check if A Binary Tree is Symmetric
One way of thinking a binary tree is symmetric is that its left and right sub trees are mirrored. Then, we can define a recursive function to check if two sub trees are symmetric.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSymmetricTree(self, root): if root is None: return True def symmetric(a, b): if a is None and b is None: return True if a is None or b is None: return False return a.val == b.val and symmetric(a.left, b.right) and symmetric(a.right, b.left) return symmetric(root.left, root.right) |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSymmetricTree(self, root):
if root is None:
return True
def symmetric(a, b):
if a is None and b is None:
return True
if a is None or b is None:
return False
return a.val == b.val and symmetric(a.left, b.right) and symmetric(a.right, b.left)
return symmetric(root.left, root.right)Time complexity is O(N) where N is the number of the nodes in the given binary tree.
Algorithms to Check if a Binary Tree is Symmetric
- Teaching Kids Programming – Iterative Algorithm to Check if a Binary Tree is Symmetric
- Teaching Kids Programming – Revisit the Symmetric Binary Tree by Using Clone and Invert Algorithm
- Teaching Kids Programming – Recursive Algorithm to Determine if a Binary Tree is Symmetric
- How to Check Symmetric Tree in C++ (Iterative and Recursion)?
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
466 wordsloading...
Last Post: Depth First Search Algorithm to Perform Phone Number Permutations
Next Post: Math Algorithm to Count Substrings With All 1s
