I created an algorithm to compare if two trees have the same leaves.
https://i.sstatic.net/lpO2C.png
Both trees display matching leaf numbers in the exact order, resulting in a true outcome.
Below is the code that I formulated:
function leafSimilar(root1: TreeNode | null, root2: TreeNode | null): boolean {
console.log(DFS(root1))
const leavesRoot1 = DFS(root1);
const leavesRoot2 = DFS(root2);
for (let i = 0; i < Math.max(leavesRoot1.length, leavesRoot2.length); i += 1) {
if (leavesRoot1[i] !== leavesRoot2[i]) {
return false;
}
}
return true;
};
function DFS(root, leaves = [] ) {
if(!root) return leaves;
if (!root.left && !root.right) {
leaves.push(root.val);
return leaves;
}
// return DFS(root.left).concat(DFS(root.right)); // this is the correct answer
return DFS(root.left, leaves).concat(DFS(root.right, leaves)); // why doesn't this work?
}
The final line of the code was my initial assumption, but it turned out to be incorrect.
I struggled to visualize it mentally, so I logged them as shown in the second-to-last line.
This log reveals:
[
6, 7, 4,
6, 7, 4,
6, 7, 4,
6, 7, 4, 9, 8,
6, 7, 4, 9, 8
]
After spending two hours trying to decipher this issue, I still cannot comprehend why.
My expectation would be something like this:
[6,
6, 7,
6, 7, 4,
6, 7, 4, 9,
6, 7, 4, 9, 8,
]
or simply
[6,7,4,9,8]
which represents the accurate result.
Can anyone provide insights into why this discrepancy exists?
The DFS function accepts the leaves array argument from the previous call.
Therefore, it is anticipated to receive leaves from the preceding node, not the following one, preventing any repetitive pattern in the leaves array since it starts empty.
As per the code I crafted, the DFS operates in preorder manner where the left-most nodes are assessed first.
I am seeking clarification on this matter. Thank you.