572. Subtree of Another Tree

Description

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Constraints

Approach

Examples

Input:

s = [3, 4, 5, 1, 2]

t = [4, 1, 2]

Output: true

Solutions

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { 
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Time complexity : O(m^2 + n^2 + m*n). A total of n nodes of the tree s and m 
 *    nodes of tree t are traversed. Assuming string concatenation takes O(k) 
 *    time for strings of length k and indexOf takes O(m*n).
 * Space complexity : O(max(m,n)). The depth of the recursion tree can go 
 *    upto n for tree t and m for tree s in worst case.
 */

public class Solution {
    HashSet < String > trees = new HashSet < > ();
    public boolean isSubtree(TreeNode s, TreeNode t) {
        String tree1 = preorder(s, true);
        String tree2 = preorder(t, true);
        return tree1.indexOf(tree2) >= 0;
    }
    public String preorder(TreeNode t, boolean left) {
        if (t == null) {
            if (left)
                return "lnull";
            else
                return "rnull";
        }
        return "#"+ t.val + " " + preorder(t.left, true) + " " + 
                preorder(t.right, false);
    }
}

/**
 * Time complexity : O(m*n). In worst case(skewed tree) traverse function 
 *    takes O(m*n) time.
 * Space complexity : O(n). The depth of the recursion tree can go upto n. 
 *    n refers to the number of nodes in s.
 */
 
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null) {
            return false;
        }
        return isSameTree(s, t) || isSubtree(s.left, t) || 
                isSubtree(s.right, t);
    }
    
    private boolean isSameTree(TreeNode n1, TreeNode n2) {
        if(n1 == null && n2 == null) {
            return true;
        }
        if(n1 == null || n2 == null) {
            return false;
        }
        return n1.val == n2.val && isSameTree(n1.left, n2.left) && 
                isSameTree(n1.right, n2.right);
    }
}

Follow up

Previous567. Permutation in String Next575. Distribute Candies

Last updated 4 years ago

Was this helpful?