Gần đây tôi đã có cơ hội dạy các học sinh trung học cách viết mã. Không có nhiều hướng dẫn thân thiện với người mới bắt đầu về các thuật toán được mã hóa bằng JavaScript, ngôn ngữ mà họ đang học. Vì vậy, tôi quyết định làm một cái.
Trong bài viết này, tôi sẽ cố gắng hết sức để giải thích một số thuật toán cốt lõi mà bạn nên tìm hiểu trước khi phỏng vấn lập trình.
Nếu bạn không quen thuộc với khái niệm cây nhị phân, tôi khuyên bạn nên xem trang wikipedia. Nếu bạn hoàn toàn nắm vững các thuật toán cơ bản đó, bạn sẽ dễ dàng giải các bài toán phức tạp hơn.
Cây tìm kiếm nhị phân (BST) là gì?
Thường thấy trong các cuộc phỏng vấn viết mã, BST là một cấu trúc dữ liệu dạng cây với một gốc duy nhất ở trên cùng. Chúng là một cách tuyệt vời để lưu trữ các giá trị số vì bản chất được sắp xếp theo thứ tự của chúng cho phép tìm kiếm và tra cứu nhanh chóng.
So với một cây bình thường, BST có các đặc tính sau:
- mọi con bên trái có giá trị nhỏ hơn cha của nó
- mọi con bên phải có giá trị lớn hơn cha của nó
- mỗi nút có thể chứa từ 0 đến 2 nút con.
Sơ đồ sau đây sẽ làm rõ mọi thứ hơn một chút.
Định nghĩa nút cây nhị phân
Chúng tôi thường xác định Nút cây nhị phân với chức năng sau trong Javascript:
function TreeNode(val, left, right) {
this.val = val
this.left = left
this.right = right
}
Giao dịch cơ bản của cây nhị phân (Đặt hàng, Đặt hàng sau, Đặt hàng trước)
Điều đầu tiên cần biết là cách lặp qua từng nút của BST. Điều này cho phép chúng tôi thực hiện một chức năng trên tất cả các nút trong BST của chúng tôi. Ví dụ, nếu chúng ta muốn tìm một giá trị x trong BST của chúng tôi, chúng tôi cần các nút.
Có ba cách chính để làm điều này. May mắn thay, họ chia sẻ các chủ đề chung.
duyệt đơn hàng
Thuật toán đệ quy là cách dễ nhất để bắt đầu với duyệt theo thứ tự cây nhị phân. Ý tưởng là như sau:
- Nếu nút là null, không làm gì cả – nếu không, hãy gọi đệ quy hàm trên nút con bên trái của nút.
- Sau đó, thực hiện một số thao tác trên nút sau khi duyệt qua tất cả các nút con bên trái. Nút hiện tại của chúng tôi được đảm bảo là nút bên trái nhất.
- Cuối cùng, gọi hàm trên node.right.
Thuật toán Inorder đi qua các nút cây từ trái, đến giữa, sang phải.
/**
* @param {TreeNode} root
*/
const inorder = (root) => {
const nodes = []
if (root) {
inorder(root.left)
nodes.push(root.val)
inorder(root.right)
}
return nodes
}
// for our example tree, this returns [1,2,3,4,5,6]
truyền tải sau khi đặt hàng
Thuật toán đệ quy là cách dễ nhất để bắt đầu với quá trình duyệt theo thứ tự sau.
- Nếu nút là null, không làm gì cả – nếu không, hãy gọi đệ quy hàm trên nút con bên trái của nút.
- Khi không còn con trái nào, hãy gọi hàm trên node.right.
- Cuối cùng, thực hiện một số thao tác trên nút.
Truyền tải theo thứ tự truy cập các nút cây từ trái, sang phải, đến giữa.
/**
* @param {TreeNode} root
*/
const postorder = (root) => {
const nodes = []
if (root) {
postorder(root.left)
postorder(root.right)
nodes.push(root.val)
}
return nodes
}
// for our example tree, this returns [1,3,2,6,5,4]
Đặt hàng trước
Thuật toán đệ quy là cách dễ nhất để bắt đầu với quá trình truyền tải đơn đặt hàng trước.
- Nếu nút là null, không làm gì cả – nếu không, hãy thực hiện một số thao tác trên nút.
- Đi qua nút con bên trái của nút và lặp lại.
- Đi qua con bên phải của nút và lặp lại.
Truyền tải theo thứ tự truy cập các nút của cây từ giữa, sang trái, sang phải.
/**
* @param {TreeNode} root
*/
const preorder = (root) => {
const nodes = []
if (root) {
nodes.push(root.val)
preorder(root.left)
preorder(root.right)
}
return nodes
}
// for our example tree, this returns [4,2,1,3,5,6]
Cây tìm kiếm nhị phân hợp lệ là gì?
Cây tìm kiếm nhị phân (BST) hợp lệ có TẤT CẢ các con bên trái có giá trị nhỏ hơn nút cha và TẤT CẢ các con bên phải có giá trị lớn hơn nút cha.
Để xác minh xem một cây có phải là cây tìm kiếm nhị phân hợp lệ hay không:
- Xác định giá trị tối thiểu và tối đa mà nút hiện tại có thể có
- Nếu giá trị của một nút không nằm trong các giới hạn đó, hãy trả về false
- Xác thực đệ quy các phần tử con bên trái của nút, với giới hạn tối đa được đặt thành giá trị của nút
- Xác thực đệ quy các con bên phải của nút, với giới hạn tối thiểu được đặt thành giá trị của nút
/**
* @param {TreeNode} root
*/
const isValidBST = (root) => {
const helper = (node, min, max) => {
if (!node) return true
if (node.val <= min || node.val >= max) return false
return helper(node.left, min, node.val) && helper(node.right, node.val, max)
}
return helper(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
}
Cách tìm độ sâu tối đa của cây nhị phân
Ở đây, thuật toán đang cố gắng tìm chiều cao/độ sâu của BST của chúng tôi. Nói cách khác, chúng tôi đang xem BST chứa bao nhiêu ‘cấp độ’.
- Nếu nút là null, chúng tôi trả về 0 vì nó không thêm bất kỳ độ sâu nào
- Nếu không, chúng tôi thêm + 1 vào độ sâu hiện tại của chúng tôi (chúng tôi đã vượt qua một cấp độ)
- Tính toán đệ quy độ sâu của nút con và trả về tổng tối đa giữa node.left và node.right
/**
* @param {TreeNode} root
*/
const maxDepth = function(root) {
const calc = (node) => {
if (!node) return 0
return Math.max(1 + calc(node.left), 1 + calc(node.right))
}
return calc(root)
};
Cách tìm Tổ tiên chung thấp nhất giữa hai nút cây
Hãy tăng độ khó lên. Làm cách nào để tìm tổ tiên chung giữa hai nút cây trong cây nhị phân của chúng ta? Hãy xem xét một số ví dụ.
Trong cây này, tổ tiên chung thấp nhất của 3 và 1 là 2. LCA của 3 và 2 là 2. LCA của 6 và 1 và 6 là 4.
Xem mô hình ở đây? LCA giữa hai nút cây là một trong các nút đó (trường hợp 3 và 2) hoặc nút cha nơi con đầu tiên được tìm thấy ở đâu đó trong cây con bên trái của nó và con thứ hai ở đâu đó trong cây con bên phải của nó.
Thuật toán tìm tổ tiên chung thấp nhất (LCA) giữa hai nút cây p và q như sau:
- Xác minh nếu p hoặc q được tìm thấy trong cây con bên trái hoặc cây con bên phải
- Sau đó, xác minh xem nút hiện tại là p hay q
- Nếu một trong số p hoặc q được tìm thấy ở cây con bên trái hoặc bên phải và một trong số p hoặc q là chính nút đó, thì chúng ta đã tìm thấy LCA
- Nếu cả p và q đều được tìm thấy ở cây con bên trái hoặc bên phải, chúng ta đã tìm thấy LCA
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
*/
const lowestCommonAncestor = function(root, p, q) {
let lca = null
const isCommonPath = (node) => {
if (!node) return false
var isLeft = isCommonPath(node.left)
var isRight = isCommonPath(node.right)
var isMid = node == p || node == q
if (isMid && isLeft || isMid && isRight || isLeft && isRight) {
lca = node
}
return isLeft || isRight || isMid
}
isCommonPath(root)
return lca
};
kết thúc
Tóm lại, chúng ta đã học cách duyệt, xác minh và tính toán độ sâu của BST.
Các thuật toán này thường được hỏi về các cuộc phỏng vấn mã hóa. Điều quan trọng là phải hiểu chúng trước khi thực hành các ứng dụng BST nâng cao hơn, chẳng hạn như tìm LCA của hai nút.
