572. Subtree of Another Tree(另一个树的子树)
572. Subtree of Another Tree(另一个树的子树)
题目地址:https://leetcode.com/problems/subtree-of-another-tree/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 sand 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 2Given tree t:
4
/ \
1 2Return 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
/
0Given tree t:
4
/ \
1 2Return false.
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1: 给定的树 s:
3
/ \
4 5
/ \
1 2给定的树 t：
4
/ \
1 2返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2: 给定的树 s：
3
/ \
4 5
/ \
1 2
/
0给定的树 t：
4
/ \
1 2返回 false。
/**
* 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 || t == null) return s == t;
if (isSame(s, t)) return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
public boolean isSame(TreeNode s, TreeNode t) {
if (s == null || t == null) return s == t;
return s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right);
}
}
题目输入的测试是s是[3, 4, 5, 1, 2, null, null, 0]，t是[4, 1, 2]的形式，从上到下按层遍历建树
Debug code in playground:
/* -----------------------------------
* WARNING:
* -----------------------------------
* Your code may fail to compile
* because it contains public class
* declarations.
* To fix this, please remove the
* "public" keyword from your class
* declarations.
*/
/**
* 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 || t == null) return s == t;
if (isSame(s, t)) return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
public boolean isSame(TreeNode s, TreeNode t) {
if (s == null || t == null) return s == t;
return s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right);
}
}
public class MainClass {
public static TreeNode stringToTreeNode(String input) {
input = input.trim();
input = input.substring(1, input.length() - 1);
if (input.length() == 0) {
return null;
}
String[] parts = input.split(",");
String item = parts[0];
TreeNode root = new TreeNode(Integer.parseInt(item));
Queue<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
int index = 1;
while(!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
if (index == parts.length) {
break;
}
item = parts[index++];
item = item.trim();
if (!item.equals("null")) {
int leftNumber = Integer.parseInt(item);
node.left = new TreeNode(leftNumber);
nodeQueue.add(node.left);
}
if (index == parts.length) {
break;
}
item = parts[index++];
item = item.trim();
if (!item.equals("null")) {
int rightNumber = Integer.parseInt(item);
node.right = new TreeNode(rightNumber);
nodeQueue.add(node.right);
}
}
return root;
}
public static String booleanToString(boolean input) {
return input ? "True" : "False";
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = in.readLine()) != null) {
TreeNode s = stringToTreeNode(line);
line = in.readLine();
TreeNode t = stringToTreeNode(line);
boolean ret = new Solution().isSubtree(s, t);
String out = booleanToString(ret);
System.out.print(out);
}
}
}