In this problem,Nodes with duplicate values are not present.
class Solution {
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
if (root1 == root2)
return true;
if (root1 == null || root2 == null || root1.val != root2.val)
return false;
return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right) ||
flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
}
}
What would be the time complexity of this code if node with duplicate values were also present??
How Can I improve my code so that it also works with duplicate values?
Thanks in Advance:)
How would the presence of duplicate values make a difference?
See this photo
see this above photo. What will be the time complexity for this example
I think it can be done in two pass of DFS .
In first pass (post-order) we will swap the children if the subtress don't match at current root .
Second pass will be for verifying that whether they are both same or not . O(2*n) .