🏒

剑指 Offer 26. 树的子结构

💛
难度: 中等

题目

输入两棵二叉树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相等
 
  1. 如果根节点相同
    1. 继续判断A和B的左,子树和右子树是否也相等, 都相等则满足条件, 不相等则不满足条件
  1. 如果根节点不相同, 此时A的左子树或右子树和B相等都满足条件
    1. 递归判断A的左子树是否和B相等
    2. 递归判断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

优化点