leetcode 572题

leetcode 572 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例1

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例2

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

思路

判断 s 是不是 t 的子树，有三种情况

s 和 t 完全相同，也就是一颗相同的树
s.left 和 t 中相等
s.right 和 t 中相等

由此可以知道，需要判断三种情况，通过 dfs 遍历两棵树，当两者的当前节点都是 null 的时候，则表示是 true，否则是 false

代码

/**
 * @param {TreeNode} root
 * @param {TreeNode} subRoot
 * @return {boolean}
 */
function isSubtree(s, t) {
    if (s === null) {
        return false;
    }

    return check(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

function check(a, b) {
    if (a === null && b === null) {
        return true;
    }
    if (a === null || b === null) {
        return false;
    }
    if (a.val === b.val) {
        return check(a.left, b.left) && check(a.right, b.right);
    }
    return false;
}

复杂度分析:

时间复杂度: O(logN)
空间复杂度：O(1)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python

leetcode 572 另一棵树的子树

思路

代码

CATALOG

FEATURED TAGS

FRIENDS