二叉树是否是子树

算法思路

给定两棵二叉树 s 和 t，判断 t 是否为 s 的子树（在 s 的某个节点处，存在一棵与 t 结构和值完全相同的子树）。

在 s 的每个节点上尝试「以该节点为根是否与 t 相同」，用「两树是否相同」的递归判断；若当前节点不匹配，再递归 s 的左、右子树。

• t 为空 → 视为任意树的子树，返回 true
• s 为空且 t 非空 → 返回 false
• 否则：is_same_tree(s, t) 或 is_subtree(s.left, t) 或 is_subtree(s.right, t)

时间 O(m × n)（m、n 为两树节点数），空间 O(h)（h 为 s 的高度，递归栈）。

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_same_tree(p: TreeNode, q: TreeNode) -> bool:
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)


def is_subtree(s: TreeNode, t: TreeNode) -> bool: #t是子树
    if not t:
        return True
    if not s:
        return False
    if is_same_tree(s, t):
        return True
    return is_subtree(s.left, t) or is_subtree(s.right, t)

js

function TreeNode(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function isSameTree(p, q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    if (p.val !== q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

function isSubtree(s, t) {
    if (!t) return true;
    if (!s) return false;
    if (isSameTree(s, t)) return true;
    return isSubtree(s.left, t) || isSubtree(s.right, t);
}

go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isSameTree(p, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    if p.Val != q.Val {
        return false
    }
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

func isSubtree(s, t *TreeNode) bool {
    if t == nil {
        return true
    }
    if s == nil {
        return false
    }
    if isSameTree(s, t) {
        return true
    }
    return isSubtree(s.Left, t) || isSubtree(s.Right, t)
}