Giải Thuật Leetcode 572 Cây Con của Một Cây Khác - nổ hũ mạt chược

Giới Thiệu Bài Toán

Cho hai cây nhị phân có gốc lần lượt là root và subRoot, hãy trả về true nếu tồn tại một cây con của root có cùng cấu trúc và giá trị nút với subRoot. Ngược lại, trả về false. Một cây con của cây nhị phân được định nghĩa là một cây bao gồm một nút trong cây và tất cả các nút con của nó. Lưu ý rằng chính cây root cũng có thể được coi là một cây con của chính nó.

Ví Dụ 1

Đầu vào: root [bắn cá ăn xu online](/blog/3406772f3a2a5546.html) = [3,4,5,1,2], subRoot = [4,1,2]
Đầu ra: true

Ví Dụ 2

[

Đầu vào: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Đầu ra: false ]

Phân Tích Bài Toán

Bài toán yêu cầu kiểm tra xem cây có gốc subRoot có phải là một cây con của cây có gốc root hay không. Điều này có vẻ đơn giản khi bạn hiểu rõ khái niệm "cây con". Quan trọng ở đây là chúng ta đang nói đến một cây con hoàn chỉnh, chứ không phải chỉ là một phần cấu trúc nào đó. Ví dụ như trong ví dụ thứ hai, mặc dù cây con bên trái của root có cấu trúc gần giống với subRoot, nhưng sự hiện diện của nút 0 khiến nó không thể được coi là một cây con hoàn chỉnh. Do đó, kết quả là false.

Phương pháp giải quyết bài toán này khá trực tiếp:

1. Sử dụng đệ quy để tìm kiếm nohu95 trong cây root một nút có giá trị trùng khớp với nút gốc của subRoot.
2. Sau khi tìm thấy nút phù hợp, sử dụng một hàm khác (đệ quy) để so sánh toàn bộ cấu trúc của hai cây, đảm bảo rằng mọi nút con đều giống nhau.

Mã Nguồn

 1public boolean isSubtree(TreeNode root, TreeNode subRoot) {
 2    // Nếu subRoot hoặc root là null, trả về false
 3    if (subRoot == null || root == null) {
 4        return false;
 5    }
 6    
 7    // Kiểm tra nếu giá trị của root và subRoot bằng nhau
 8    if (root.val == subRoot.val) {
 9        // So sánh toàn bộ cây từ đây
10        if (isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right)) {
11            return true;
12        }
13    }
14    
15    // Nếu chưa tìm thấy, tiếp tục tìm kiếm trong cây con trái và phải
16    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
17}
18
19// Hàm kiểm tra hai cây có giống nhau hoàn toàn hay không
20public boolean isSameTree(TreeNode root, TreeNode subTree) {
21    // Nếu cả hai nút đều là null, chúng giống nhau
22    if (root == null && subTree == null) {
23        return true;
24    }
25    
26    // Nếu một trong hai nút là null, mà nút kia không phải, thì khác nhau
27    if (root == null || subTree == null) {
28        return false;
29    }
30    
31    // Nếu giá trị của hai nút khác nhau, trả về false
32    if (root.val != subTree.val) {
33        return false;
34    }
35    
36    // Tiếp tục so sánh các cây con trái và phải
37    return isSameTree(root.left, [nổ hũ mạt chược](/blog/2f2ab9c50c37df85.html)  subTree.left) && isSameTree(root.right, subTree.right);
38}