572. Subtree of Another Tree - Easy

前往題目

想法

• 找subRoot在原樹的位置
• 找到後直接開始檢查兩樹是否一樣

思路

1. 檢查兩樹的是否為空，subRoot樹空代表一定是true，因為null是所有樹的子樹；而root樹空如果subRoot樹也為空，那也是true
2. 往左右子樹前進，每次都檢查是否兩樹為相同樹

Time: $O(M * N)$ 因為每個節點都檢查是否為相同樹

Code (WA)

明明簡單，但好像沒那麼簡單…不知道哪裡出了問題

// WA
class Solution {
    TreeNode subRootInTree;
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) return true;
        if (root == null) return false;
        // Find the position of the root of the subRoot
        subRootPos(root, subRoot);
        // Check if exists
        if (subRootInTree == null) return false;
        // Check if the same
        return check(root, subRootInTree);
    }

    private void subRootPos(TreeNode node, TreeNode subRoot) {
        if (node == null) return;
        if (node.val == subRoot.val) {
            subRootInTree = node;
            return;
        }

        // Search
        subRootPos(node.left, subRoot);
        subRootPos(node.right, subRoot);

        return;
    }

    private boolean check(TreeNode node1, TreeNode node2) {
        if (node1.val != node2.val) return false;

        check(node1.left, node2.left);
        check(node1.right, node2.right);

        return true;
    }
}

Code (AC)

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // null is def. a subtree of root
        if (subRoot == null) return true;
        // def. false if no root to check
        if (root == null) return false;

        // return true if they are the same tree
        if (sameTree(root, subRoot)) return true;

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

    private boolean sameTree(TreeNode node, TreeNode subRoot) {
        // Both reached the end
        if (node == null && subRoot == null) return true;

        // Keep searching
        if (node != null && subRoot != null && node.val == subRoot.val) {
            return sameTree(node.left, subRoot.left) && sameTree(node.right, subRoot.right);
        }

        // Doesn't correspond
        return false;
    }
}