R.A.N.K.A.'s blog

Time Complexity of LeetCode Problem 951
By R.A.N.K.A., history, 4 years ago, In English

Problem Link

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:)

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

How would the presence of duplicate values make a difference?

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

See this photo

see this above photo. What will be the time complexity for this example

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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) .

→ Reply