题目描述:输入两棵二叉树 A,B,判断 B 是不是 A 的子结构。(ps:我们约定空树不是任意一个树的子结构)。
输入两棵二叉树 A,B,判断 B 是不是 A 的子结构。(ps:我们约定空树不是任意一个树的子结构)。
为了方便说明,先看两个例子。
下图是第一个例子,可以看到 B 是 A 的子结构。
第一个例子的判断逻辑是:
下图是第二个例子,可以看到 B 也是 A 的子结构。
但是 A 的根节点和 B 的根节点并不相同。因此对于这种情况,需要对 A 树进行递归遍历。如果 B 是 A 的左子树或者右子树的子结构,那么也是可以的。
设计两个函数:
// ac地址:https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
// 原文地址:https://xxoo521.com/2020-01-13-subtree/
/**
* 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 || !B) {
return false;
}
return (
isSubTree(A, B) ||
isSubStructure(A.left, B) ||
isSubStructure(A.right, B)
);
};
function isSubTree(pRoot1, pRoot2) {
// B树遍历完了,说明B是A的子结构
if (!pRoot2) {
return true;
}
// A遍历完了,但是B还没有遍历完,那么B肯定不是A的子结构
if (!pRoot1) {
return false;
}
if (pRoot1.val !== pRoot2.val) {
return false;
}
return (
isSubTree(pRoot1.left, pRoot2.left) &&
isSubTree(pRoot1.right, pRoot2.right)
);
}