Subtree of Another Tree

Given two non-empty binary treessandt, check whether treethas exactly the same structure and node values with a subtree ofs. A subtree ofsis a tree consists of a node insand all of this node's descendants. The treescould also be considered as a subtree of itself.

Example 1: Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

 4 
  / \
 1   2

Return

true

, because t has the same structure and node values with a subtree of s.

Example 2: Given tree s:

   3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

 4
  / \
 1   2

Return

false

Solution 1:

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

        if(s == null){
            return false;
        }

        if(t == null){
            return false;
        }

        bool flag = IsChecked(s, t);
        if(flag){
            return true;
        }

        return IsSubtree(s.left, t) || IsSubtree(s.right, t);
    }

    public bool IsChecked(TreeNode s, TreeNode t){

        if(s == null && t == null){
            return true;
        }

        if(s == null || t == null){
            return false;
        }

        bool left = IsChecked(s.left, t.left);
        bool right = IsChecked(s.right, t.right);

        return left && right && s.val == t.val;
    }
}

Solution 2:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSubtree(TreeNode s, TreeNode t) {

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(s);

        while(stack.Count > 0){
            TreeNode node = stack.Pop();
            if(node.val == t.val){
                bool flag =IsChecked(node, t);
                if(flag){
                    return flag;
                }
            }
            if(node.right != null){
                stack.Push(node.right);
            }

            if(node.left != null){
                stack.Push(node.left);
            }

        }
        return false;
    }

    public bool IsChecked(TreeNode s, TreeNode t){

        if(s == null && t == null){
            return true;
        }

        if(s == null || t == null){
            return false;
        }

        bool left = IsChecked(s.left, t.left);
        bool right = IsChecked(s.right, t.right);

        return left && right && s.val == t.val;
    }
}