1. Description

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.

2. Runtime Distribution

3. Submission Details

4. Example

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.

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

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

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

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

public class LeetCode0572 {
	static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

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

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

[/restab]
[/restabs]