Độ sâu tối đa của cây nhị phân trong Python

Cho cây nhị phân, tìm độ sâu tối đa (số nút trên đường dài nhất từ gốc đến lá). Ví dụ: cây chiều sâu 3.

Giải pháp

Đệ quy:

• Hàm solve(root, depth=0).
• Nếu root rỗng → return depth.
• Trả về max(solve(left, depth+1), solve(right, depth+1)).

Ví dụ

Triển khai Python:

class TreeNode: 
    def __init__(self, data, left = None, right = None): 
        self.data = data 
        self.left = left 
        self.right = right 
# ... (hàm hỗ trợ tạo cây) 
class Solution(object): 
    def maxDepth(self, root): 
        return self.solve(root) 
    def solve(self,root,depth = 0): 
        if root == None: 
            return depth 
        return max(self.solve(root.left,depth+1),self.solve(root.right,depth+1)) 
tree1 = make_tree([1,2,2,3,4,None,3]) 
ob1 = Solution() 
print(ob1.maxDepth(tree1))

Đầu vào

tree1 = make_tree([1,2,2,3,4,None,3])

Đầu ra

3