难度: 中等
题目
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B:
4
/
1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1:
输入:A = [1,2,3], B = [3,1]
输出:false
示例 2:
输入:A = [3,4,5,1,2], B = [4,1]
输出:true
提示:
0 <= 节点个数 <= 10000
思路
DFS 深度优先遍历
对于两个节点来说一共有三种情况可以满足条件 (满足任意一种即可)
- A和B的根部相等, A和B的左右子树都相等
- A和B的根部不相等, A的左子树和B相等
- A和B的根部不相等, A的右子树和B相等
- 如果根节点相同
- 继续判断A和B的左,子树和右子树是否也相等, 都相等则满足条件, 不相等则不满足条件
- 如果根节点不相同, 此时A的左子树或右子树和B相等都满足条件
- 递归判断A的左子树是否和B相等
- 递归判断A的右子树是否和B相等
此外还需要注意判断 null 的边界情况
题解
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} A
* @param {TreeNode} B
* @return {boolean}
*/
var isSubStructure = function(A, B) {
// 约定空树不是任意一个树的子结构
if (A === null || B === null) {
return false
}
// B初次不为null, 如果B递归到null, 说明B已经递归到底
const isSame = (A, B) => {
if (B === null) return true
if (A === null) return false
return A.val === B.val && isSame(A.left, B.left) && isSame(A.right, B.right)
}
return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
};
结果
执行用时:116 ms, 在所有 JavaScript 提交中击败了51.17%的用户
内存消耗:57.1 MB, 在所有 JavaScript 提交中击败了63.16%的用户
通过测试用例:48 / 48