Chương trình tìm độ dài đường đi xen kẽ trái-phải dài nhất trong cây nhị phân bằng Python

Cho cây nhị phân. Tìm đường đi dài nhất xen kẽ giữa con trái và con phải khi đi xuống (zigzag path).

Ví dụ: cây minh họa → 5 (đường [2,4,5,7,8]).

Giải thuật

• DFS trả về độ dài đường xen kẽ dài nhất từ nút hiện tại.
• Tham số flag: True nghĩa là bước trước đi trái (nay phải đi phải), False ngược lại.
• Nếu flag=True: a = dfs(left, count+1, False), b = dfs(right, 1, True).
• Nếu flag=False: a = dfs(right, count+1, True), b = dfs(left, 1, False).
• Trả về max(a,b).
• Gọi từ gốc: max(dfs(root.left,1,False), dfs(root.right,1,True)).

Ví dụ minh họa

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

class Solution:
    def solve(self, root):
        if not root:
            return 0
        def dfs(node, count, flag):
            if node:
                if flag == True:
                    a = dfs(node.left, count+1, False)
                    b = dfs(node.right, 1, True)
                elif flag == False:
                    a = dfs(node.right, count+1, True)
                    b = dfs(node.left, 1, False)
                return max(a, b)
            return count
        a = dfs(root.left, 1, False)
        b = dfs(root.right, 1, True)
        return max(a, b)

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)
print(ob.solve(root))

Đầu vào

root = TreeNode(2) ...

Đầu ra

5