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)
    
    

All Problems

All Solutions