## 判断是否为一棵树的子树 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也可以是自己本身的一个子树

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution { //28ms
public boolean isSubtree(TreeNode s, TreeNode t) {
if(t == null) return true;
if(s == null) return false;
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 true;
if(s == null || t == null) return false;
if(s.val != t.val) return false;
return isSame(s.left,t.left) && isSame(s.right,t.right);
}
}

② 在discuss中看到以下解法

public class Solution { // 16ms
public boolean isSubtree(TreeNode s, TreeNode t) {
return isSubtree(s, t, true);
}
private boolean isSubtree(TreeNode s, TreeNode t, boolean isHead) {
if (s == null && t == null) return true;
if (s == null || t == null || (s.val != t.val && !isHead)) return false; //isHead表示是否以当前节点为根节点比较子树的
if (s.val == t.val) {
boolean left = isSubtree(s.left, t.left, false);
boolean right = isSubtree(s.right, t.right, false);
if (left && right) {
return true;
} else {
left = isSubtree(s.left, t, true);
right = isSubtree(s.right, t, true);
return left || right;
}
} else {
boolean left = isSubtree(s.left, t, true);
boolean right = isSubtree(s.right, t, true);
return left || right;
}
}
}

### 叶枫啦啦

LeetCode572. Subtree of Another Tree (另一个棵树的子树)

dby_freedom
2018/12/18
0
0
LeetCode 98. Validate Binary Search Tree (有效二叉搜索树)

dby_freedom
2018/12/03
0
0

T1是一棵含有几百万个节点的树，T2含有几百个节点。判断T2是否是T1 的子树。 首先考虑小数据量的情况，可以根据树的前序和中序遍历所得的字符串，来通过判断T2生成的字符串是否是T1字符串的子...

2016/11/18
92
0

2016/12/20
8
0
[LeetCode] Count Univalue Subtrees 计数相同值子树的个数

/ 1 5/ 5 5 5 public: }; 解法二： class Solution {public: }; 我们还可以变一种写法，让递归函数直接返回以当前节点为根的相同值子树的个数，然后参数里维护一个引用类型的布尔变量，表示以...

2017/12/15
0
0

Handler简解

Handler 这里简化一下代码 以便理解 Handler不一定要在主线程建 但如Handler handler = new Handler(); 会使用当前的Looper的, 由于要更新UI 所以最好在主线程 new Handler() { mLooper = Lo...

shzwork
19分钟前
2
0
h5获取摄像头拍照功能

22分钟前
2
0

38分钟前
3
0
5个避免意外论文重复率高的方法

40分钟前
3
0
Maven通过profiles标签读取不同的配置

<profiles> <profile> <id>dev</id> <properties> <profiles.active>dev</profiles.active> </properties> ......

45分钟前
1
0