leetcode/java/572-Subtree-of-Another-Tree.java at main · remenraj/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Solution: Recursive Approach

// Time Complexity: O(n)
// Extra Space Complexity: O(n)
class Solution1 {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }

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

    private boolean isSameTree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        if (root.val == subRoot.val) {
            return (
                isSameTree(root.left, subRoot.left) &&
                isSameTree(root.right, subRoot.right)
            );
        }

        return false;
    }
}