Subtree of Another Tree

https://leetcode.com/problems/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.

Thoughts

分治法，当左右子树都不包含t时，就只剩以当前结点为root的树和t一样了。因此直接调用isSame(s, t)即可。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) { 
            return true;
        } else if (s == null || t == null) {
            return false;
        }

        if (s.val != t.val) {
            return false;
        }

        boolean left = isSame(s.left, t.left);
        boolean right = isSame(s.right, t.right);

        return left && right;
    }

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) {
            return false;
        }

        boolean left = isSubtree(s.left, t);
        boolean right = isSubtree(s.right, t);

        if (left || right) {
            return true;
        } else {
            return isSame(s, t);
        }
    }
}

Analysis

时间杂度为O(nm), 空间复杂度O(1). 因为最差时不是子树, 那么每个节点都要调用一次isSame.

Ver.2

直观的想法是两个都转成String, 然后用KMP等strStr匹配，需要O(n+m)时间复杂度和O(n+m)空间复杂度。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                sb.append(",").append(node.val);
                stack.push(node.left);
                stack.push(node.right);
            } else {
                sb.append(",#");
            }
        }
        return sb.toString();
    }

    public boolean isSubtree(TreeNode s, TreeNode t) {
        String strS = serialize(s);
        String strT = serialize(t);
        return strS.contains(strT);
    }
}