Given a binary tree root, return whether all leaves are at the same level.
Constraints
n ≤ 100,000 where n is the number of nodes in root
Breadth First Search Algorithm to Record the Depths of All Leave Nodes
We can use the BFS aka Breadth First Search Algorithm to Record all the depths values of all leaf nodes in a set. Then finally we can check if there is only one (unique) number in the set. If yes, we confirm all the leaf nodes are in the same level.
C++ BFS to check all the nodes are in the same levels is as follows:
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 26 27 28 29 30 | /** * class Tree { * public: * int val; * Tree *left; * Tree *right; * }; */ bool sameLevelsForLeavesNodes(Tree* root) { if (!root) return true; unordered_set<int> leaves; queue<pair<Tree*, int>> Q; Q.push({root, 0}); while (!Q.empty()) { auto p = Q.front(); Q.pop(); auto node = p.first; auto depth = p.second; if (node->left == node->right) { // leaf node == both children NULL leaves.insert(depth); } if (node->left) { Q.push({node->left, depth + 1}); } if (node->right) { Q.push({node->right, depth + 1}); } } return leaves.size() == 1; } |
/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
bool sameLevelsForLeavesNodes(Tree* root) {
if (!root) return true;
unordered_set<int> leaves;
queue<pair<Tree*, int>> Q;
Q.push({root, 0});
while (!Q.empty()) {
auto p = Q.front();
Q.pop();
auto node = p.first;
auto depth = p.second;
if (node->left == node->right) { // leaf node == both children NULL
leaves.insert(depth);
}
if (node->left) {
Q.push({node->left, depth + 1});
}
if (node->right) {
Q.push({node->right, depth + 1});
}
}
return leaves.size() == 1;
}The time complexity is O(N) and the space complexity is also O(N) where we need to visit all the N nodes in the given binary tree.
And here is the Python implementation for the same BFS algorithm:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sameLevelsForLeavesNodes(self, root): if root is None: return True Q = deque([(root, 0)]) depths = set() while len(Q) > 0: cur, d = Q.popleft() if cur.left: Q.append((cur.left, d + 1)) if cur.right: Q.append((cur.right, d + 1)) if cur.left is None and cur.right is None: depths.add(d) return len(depths) == 1 |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sameLevelsForLeavesNodes(self, root):
if root is None:
return True
Q = deque([(root, 0)])
depths = set()
while len(Q) > 0:
cur, d = Q.popleft()
if cur.left:
Q.append((cur.left, d + 1))
if cur.right:
Q.append((cur.right, d + 1))
if cur.left is None and cur.right is None:
depths.add(d)
return len(depths) == 1We can also use Depth First Search Algorithm: Teaching Kids Programming – Depth First Search Algorithm to Check If Leaves are Same Level in Binary Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Recursive Algorithm to Convert a Sorted List to a Balanced Binary Search Tree
Next Post: Teaching Kids Programming - Divide and Conquer Algorithm to Merge K Sorted Linked List
