572. Subtree of Another Tree
Tags:
Easy
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu kiểm tra xem một subroot của binary tree nhỏ có phải là một subtree của cây lớn hơn root hay không, nghĩa là có tồn tại một node trong root mà toàn bộ cây con bắt đầu từ node đó giống hệt với subroot cả về cấu trúc lẫn giá trị node
Approach
root subroot không (cả giá trị và cấu trúc)true . Nêu không tiếp tục kiểm tra các node con bên trái và phảisameTree hoặc isSameTree ) sẽ kiểm tra: Time and space complexity
root, m là số node của subRootvì mỗi node của root có thể phải so sánh toàn bộ với subrootSolution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
16 function same(p: TreeNode | null, q: TreeNode | null): boolean {
17 if (!p && !q) return true;
18 if (!p || !q || p.val !== q.val) return false;
19 return same(p.left, q.left) && same(p.right, q.right)
20 }
21
22 if (!root) return false
23 return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
24};