Union of two binary trees (if they share common nodes)


  • 0
    A

    e.g

    Tree 1:                                         Tree 2:                                  
               A                                              B                                      
            /      \                                       /     \                                                 
         B         C                                   D            E
        /           |                                /    \          \ 
      D           ...                               C     F           G
    
    Union:                                                               
               A                                                                  
            /      \                                                                            
         B          C                              
        /   \          |                                 
       D     E         ...        
     /   \      \
    C     F      G               
    

    The union of the two trees should be returned if there is an overlap. We don't know which tree might be a subtree of the other. The result should be a new tree [inputs should not be modified]

    I proposed a recursive solution which would work if we knew that Tree2 could be a subtree of the other. If this is not assumed how do I go about it ?


  • 0
    W

    You can save all the node in Tree1 with a HashTable , then judge whether the root of Tree2 is in the HashTable.
    If true then Tree2 is a subtree of tree1 , otherwise you can assume tree1 is a subtree of Tree2.


  • 0
    A

    @ww884203 I can understand your general idea. But could you elaborate on how you would actually proceed to code it up. I think it would not be easy to find the union nodes.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.