LeetCode 572 Subtree of Another Tree

LeetCode 572 Subtree of Another Tree

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.

题目大意：

给定两个非空二叉树s和t，判断t是否是s的子树。s的子树是指由s中某节点及该节点的所有子节点构成的二叉树。
特别的，s是其本身的子树。

解题思路：

这是A公司的题目。DFS解题：

1. s树的每一个节点与t树的根节点比较，若值相等进行下一步。
2. s树的某节点为根的子树和t树进行结构+值比较。

注意事项：

1. s=null和t=null，是子树
2. s和t任一为空，另一个不为空，不是子树。

Java代码：

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

public boolean isSame(TreeNode root, TreeNode root2){
	if(root==null && root2 == null)
		return true;
	if(root==null || root2 == null)
		return false;
	return root.val==root2.val && isSame(root.left,root2.left) && isSame(root.right, root2.right);
}

算法分析：

时间复杂度为O(nm)，空间复杂度O(1)，n和m分别为s数和t数大小。

Follow-up:

如果s是BST，怎么改进算法？
二分法先找到s的节点值等于t根节点值的节点再比较。时间复杂度为O(logn+m)。

public boolean contains(TreeNode t, TreeNode node) {
	if (node == null)
		return false;
	int result = t.compareTo(node.val);
	if (result > 0)
		return contains(t, node.right);
	else if (result < 0)
		return contains(t, node.left);
	else
		return true;
}

若BST不是严格递增 (allow duplicates)，多比较几个相等节点即可。