Chương trình tìm độ dài đường đi liên tiếp dài nhất trong cây nhị phân Python

Cho cây nhị phân, tìm đường đi liên tiếp (consecutive path) dài nhất. Đường đi liên tiếp: giá trị các nút tăng hoặc giảm 1 đơn vị liên tục theo đường đi (có thể lên/xuống cây).

Ví dụ: cây có đường đi [2,3,4,5,6] → output 5.

Thuật toán DFS Post-order:

• Mỗi nút trả về (inc, dec):
  • inc: dài nhất đường tăng (giá trị +1) kết thúc tại nút này
  • dec: dài nhất đường giảm (giá trị -1) kết thúc tại nút này
• Kết hợp con trái/phải:
  • Nếu node.val - left.val == 1: inc = max(inc, left_inc + 1)
  • Nếu node.val - left.val == -1: dec = max(dec, left_dec + 1)
  • Tương tự cho con phải
• Cập nhật maxPath:
  • Đường đi qua nút (V-shape): left_dec + right_inc + 1 (giảm trái → nút → tăng phải)
  • Hoặc left_inc + right_dec + 1 (tăng trái → nút → giảm phải)
  • Cũng so sánh với inc, dec (đường thẳng)

Triển khai

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

class Solution:
    def solve(self, root):
        if not root:
            return 0
        self.maxPath = 0
        
        def helper(node):
            inc, dec = 1, 1
            
            if node.left:
                left_inc, left_dec = helper(node.left)
            else:
                left_inc, left_dec = 0, 0
            
            if node.right:
                right_inc, right_dec = helper(node.right)
            else:
                right_inc, right_dec = 0, 0
            
            # Đường tăng/giảm từ con trái
            if node.left and node.val - node.left.val == 1:
                inc = max(inc, left_inc + 1)
            elif node.left and node.val - node.left.val == -1:
                dec = max(dec, left_dec + 1)
            
            # Đường tăng/giảm từ con phải
            if node.right and node.val - node.right.val == 1:
                inc = max(inc, right_inc + 1)
            elif node.right and node.val - node.right.val == -1:
                dec = max(dec, right_dec + 1)
            
            # Đường V-shape qua nút này
            if (node.left and node.right and 
                node.left.val - node.val == 1 and node.val - node.right.val == 1):
                self.maxPath = max(self.maxPath, left_dec + right_inc + 1)
            elif (node.left and node.right and 
                  node.left.val - node.val == -1 and node.val - node.right.val == -1):
                self.maxPath = max(self.maxPath, left_inc + right_dec + 1)
            
            self.maxPath = max(self.maxPath, inc, dec)
            return inc, dec
        
        helper(root)
        return self.maxPath

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

Đầu vào

TreeNode(3) -> left=2, right=4 -> right.left=5 -> right.left.left=6, right.right=9

Đầu ra

5

Giải thích: Đường đi [2,3,4,5,6] (2→3→4→5→6). DFS post-order tính inc/dec từ lá lên gốc. Phức tạp O(n) thời gian, O(h) không gian (stack đệ quy).