Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a binary tree root, return the number of nodes that are an only child. A node x is an only child if its parent has exactly one child (x).
Constraints
n ≤ 100,000 where n is the number of nodes in root
Using BFS Algorithm to Find the Only Child in Binary Tree
We can use the BFS (Breadth First Search) Algorithm, to traverse the binary tree. While we expanding the node into the queue, we know record the number of the children for the current node. Thus, we accumulate the only child when the count is 1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def solve(self, root): if not root: return 0 q = deque([(root, -1)]) ans = 0 while q: cur, cnt = q.popleft() if cnt == 1: ans += 1 x = 0 if cur.left: x += 1 if cur.right: x += 1 if cur.left: q.append((cur.left, x)) if cur.right: q.append((cur.right, x)) return ans |
# class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def solve(self, root): if not root: return 0 q = deque([(root, -1)]) ans = 0 while q: cur, cnt = q.popleft() if cnt == 1: ans += 1 x = 0 if cur.left: x += 1 if cur.right: x += 1 if cur.left: q.append((cur.left, x)) if cur.right: q.append((cur.right, x)) return ans
The time complexty is O(N) where N is the number of the nodes in the binary tree and the space complexity is O(N) as we are using a queue to implement the BFS.
See also: Counting the Only Child in the Binary Tree using Breadth First Search Algorithm
Finding only child in binary tree can be also solved using Depth First Search Algorithm: Teaching Kids Programming – Depth First Search Algorithm to Find the Only Child in Binary Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Counting the Number of Different Integers in a String
Next Post: Finding the Second Largest Digit in a String