# 0572. Subtree of Another Tree
###### tags: `Leetcode` `FaceBook` `Easy` `DFS`
Link: https://leetcode.com/problems/subtree-of-another-tree/
## 思路 $O(MN)$ $O(N)$
M是s的node个数 N是t的node个数
用递归做会简单很多，而且比iterative快
## Code
递归

public class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s==null) return false;
        if (isSame(s, t)) return true;
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    
    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        
        if (s.val != t.val) return false;
        
        return isSame(s.left, t.left) && isSame(s.right, t.right);
    }
}

iterative

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(equalTree(curr, subRoot)) return true;
            if(curr.left!=null) q.add(curr.left);
            if(curr.right!=null) q.add(curr.right);
        }
        return false;
    }
    public boolean equalTree(TreeNode root, TreeNode subRoot){
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.add(root);
        stack2.add(subRoot);
        while(!stack1.isEmpty() && !stack2.isEmpty()){
            TreeNode curr1 = stack1.pop();
            TreeNode curr2 = stack2.pop();
            if(curr1.val!=curr2.val) return false;
            
            if(curr1.left == null){
                if(curr2.left != null) return false;
            }
            else{
                if(curr2.left == null) return false;
                else{
                    stack1.add(curr1.left);
                    stack2.add(curr2.left);
                }
            }
            
            if(curr1.right == null){
                if(curr2.right != null) return false;
            }
            else{
                if(curr2.right == null) return false;
                else{
                    stack1.add(curr1.right);
                    stack2.add(curr2.right);
                }
            }
            
        }
        return stack1.isEmpty() && stack2.isEmpty();
    }
}