572. Subtree of Another Tree

 一刷 06/2022

Version #1 Recursion

Time O(N^2)

Space O(N)

Runtime: 3 ms, faster than 96.91% of Java online submissions for Subtree of Another Tree.

Memory Usage: 47.4 MB, less than 7.96% of Java online submissions for Subtree of Another Tree.

class Solution {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        if (root == null) {

            return subRoot == null;

        }

        return isSubtreeFromRoot(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);

    }

    

    private boolean isSubtreeFromRoot(TreeNode node, TreeNode subNode) {

        if (subNode == null && node == null) {

            return true;

        }

        if (subNode == null || node == null) {

            return false;

        }

        return node.val == subNode.val && isSubtreeFromRoot(node.left, subNode.left) && isSubtreeFromRoot(node.right, subNode.right);

    }

}