Check whether a binary tree is contained in another binary tree, child tree structure should be considered


  • 0
    G

    //java method api
    public bool IsContained(TreeNode parent, TreeNode child)


  • 0

    How about this case? Is child contained in the parent binary tree?

    parent        child
    
       1            3
      / \          / \
     2   3        4   5
        / \
       4   5
      /
     6
    

    By the way the name parent-child seem to suggest that child node is a reference to one of the parent's child/grandchild nodes. Or is child a completely separate tree?


  • 0
    G

    Yes, this case is considered child is contained in parent. basically, the 'contain' means each node in child has same value as correspondent node in parent, and the structure of child tree also same as a subtree in parent.


  • 3

    Just want to share my solution here.

    public class Solution {
      
      public boolean isContained(TreeNode parent, TreeNode child) {
        // empty tree cannot contain any tree
        if (parent == null)
          return false;
        
        // empty tree can be contained by other tree
        if (child == null)
          return true;
        
        // if we found a match node, we can do the comparison from here
        if (parent.val == child.val && matchTree(parent, child))
          return true;
        
        // otherwise, we continue to search the child's root node
        return isContained(parent.left, child) || isContained(parent.right, child);
      }
      
      boolean matchTree(TreeNode t1, TreeNode t2) {
        if (t2 == null)
          return true;
        
        if (t1 == null)
          return false;
        
        if (t1.val != t2.val)
          return false;
        
        return matchTree(t1.left, t2.left) && matchTree(t1.right, t2.right);
      }
      
    }
    

Log in to reply
 

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