Leaf-Similar Trees, by LeetCode
From LeetCode: https://leetcode.com/problems/leaf-similar-trees/description/
Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is
(6, 7, 4, 9, 8).
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return
true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
Nothing really hard about this problem: do a pre-order DFS and add the leaves to a list of integer. Compare the two lists from both the roots. That's it. Code is below, cheers, Marcelo.
public class Solution
{
public bool LeafSimilar(TreeNode root1, TreeNode root2)
{
LinkedList l1 = new LinkedList();
LinkedList l2 = new LinkedList();
GetLeafValues(root1, l1);
GetLeafValues(root2, l2);
return CheckSimilarList(l1, l2);
}
private void GetLeafValues(TreeNode root, LinkedList list)
{
if (root == null) return;
if (root.left == null && root.right == null) list.AddLast(root.val);
GetLeafValues(root.left, list);
GetLeafValues(root.right, list);
}
private bool CheckSimilarList(LinkedList l1, LinkedList l2)
{
if (l1 == null && l2 == null) return true;
if (l1 == null || l2 == null) return false;
if (l1.Count != l2.Count) return false;
for (int i = 0; i < l1.Count; i++)
if (l1.ElementAt(i) != l2.ElementAt(i)) return false;
return true;
}
}
Nice idiomatic recursive solution! But is it possible to do it faster? Well, we don't really need to perform a complete in-order traversal and use so much extra memory. What we can do instead is to perform parallel iterative in-order traversals of both trees at the same time and for each pair of leaves check if they have same values. C++ code below does the trick in 0ms and beats 100% of other submissions :)
ReplyDeleteclass Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
if (root1 == root2) return true;
if (root1 == nullptr || root2 == nullptr) return false;
stack s1; s1.push(root1);
stack s2; s2.push(root2);
while (!s1.empty() && !s2.empty()) {
auto node1 = s1.top(); s1.pop();
while (node1->left || node1->right) {
if (node1->left) {
if (node1->right) s1.push(node1->right);
node1 = node1->left;
} else {
node1 = node1->right;
}
}
auto node2 = s2.top(); s2.pop();
while (node2->left || node2->right) {
if (node2->left) {
if (node2->right) s2.push(node2->right);
node2 = node2->left;
} else {
node2 = node2->right;
}
}
if (node1->val != node2->val) return false;
}
return s1.empty() && s2.empty();
}
};
I've also posted a more readable paste on LeetCode - https://leetcode.com/problems/leaf-similar-trees/discuss/198179/0ms-parallel-iterative-in-order-traversals-in-C%2B%2B
Cheers,
Taras