# 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);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/stack/tree-traversal/subtree-of-another-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.