Java

/*
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.

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.

 */

public class Subtree_of_Another_Tree {

	public static void main(String[] args) {
		Subtree_of_Another_Tree out = new Subtree_of_Another_Tree();
		Solution s = out.new Solution();

		TreeNode root = new TreeNode(3);
		root.left = new TreeNode(4);
		root.right = new TreeNode(5);
		root.left.left = new TreeNode(1);
		root.left.right = new TreeNode(2);

		TreeNode t = new TreeNode(4);
		t.left = new TreeNode(1);
		t.right = new TreeNode(2);

		System.out.println(s.isSubtree(root, t));
	}


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

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

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

	        // key is to have a same tree check, or else will be skip level same
	        return isSameTree(s, t) || isSubtree(s.left, t) || (isSubtree(s.right, t));
	    }

	    public boolean isSameTree(TreeNode s, TreeNode t) {

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

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

	    	return s.val == t.val && isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
	    }
	}
}

// OJ: https://leetcode.com/problems/shortest-unsorted-continuous-subarray
// Time: O(ST) where S and T are the node count of s and t.
// Space: O(H) where H is the height of s.
class Solution {
private:
    bool isSameTree(TreeNode* s, TreeNode* t) {
        return (!s && !t) || (s && t && s->val == t->val && isSameTree(s->left, t->left) && isSameTree(s->right, t->right));
    }
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        return isSameTree(s, t) || (s && (isSubtree(s->left, t) || isSubtree(s->right, t)));
    }
};

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
  def isSubtree(self, s, t):
    """
    :type s: TreeNode
    :type t: TreeNode
    :rtype: bool
    """

    def serialize(root):
      ans = []
      stack = [(root, 1)]
      while stack:
        node, p = stack.pop()
        if not node:
          ans.append("#")
          continue
        if p == 0:
          ans.append("|" + str(node.val))
        else:
          stack.append((node.right, 1))
          stack.append((node.left, 1))
          stack.append((node, 0))
      return ",".join(ans)

    return serialize(t) in serialize(s)

Java

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

    public boolean same(TreeNode s, TreeNode t) {
        if (s == null && t == null)
            return true;
        if (s == null || t == null)
            return false;
        return s.val == t.val && same(s.left, t.left) && same(s.right, t.right);
    }
}

// OJ: https://leetcode.com/problems/shortest-unsorted-continuous-subarray
// Time: O(ST) where S and T are the node count of s and t.
// Space: O(H) where H is the height of s.
class Solution {
private:
    bool isSameTree(TreeNode* s, TreeNode* t) {
        return (!s && !t) || (s && t && s->val == t->val && isSameTree(s->left, t->left) && isSameTree(s->right, t->right));
    }
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        return isSameTree(s, t) || (s && (isSubtree(s->left, t) || isSubtree(s->right, t)));
    }
};

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
  def isSubtree(self, s, t):
    """
    :type s: TreeNode
    :type t: TreeNode
    :rtype: bool
    """

    def serialize(root):
      ans = []
      stack = [(root, 1)]
      while stack:
        node, p = stack.pop()
        if not node:
          ans.append("#")
          continue
        if p == 0:
          ans.append("|" + str(node.val))
        else:
          stack.append((node.right, 1))
          stack.append((node.left, 1))
          stack.append((node, 0))
      return ",".join(ans)

    return serialize(t) in serialize(s)

572 - Subtree of Another Tree

All Problems

All Solutions