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)