[LeetCode] 298. Binary Tree Longest Consecutive Sequence

298. Binary Tree Longest Consecutive Sequence

Medium

Given the root of a binary tree, return the length of the longest consecutive sequence path.

A consecutive sequence path is a path where the values increase by one along the path.

Note that the path can start at any node in the tree, and you cannot go from a node to its parent in the path.

 

Example 1:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2:

Input: root = [2,null,3,2,null,1]
Output: 2
Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

 

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 104].
• -3 * 104 <= Node.val <= 3 * 104

---

문제 풀이

1. 이진 트리에서 증가하는 노드 연속 중 가장 큰 것을 찾아야한다.
2. 즉, 부모 트리에서 부터 아래로 연결되있는 노드가 1씩 연속적으로 증가하는 것만 고를 수 있다.
3. 이진 트리이기 때문에 왼쪽 오른쪽으로 재귀호출을 통해 값을 찾을 수 있다.
4. Top-Down 과 Bottom-Up 모두 연속 1 씩 증가가 아니라면 임시 저장하고 있는 길이의 값을 1로 바꿔주며 순회한다.
5. 차이점은 Top-Down 의 경우 부모노드와 현재 노드와의 비교를 해서, 현재 길이를 구해나가며 내려간다.
6. Bottom-Up 의 경우 현재 노드와 왼쪽 자식, 오른쪽 자식 노드를 비교하여 각각의 길이를 구한 뒤에 최대값을 계산한다.

소스 코드

Top-Down

class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        
        def detect(node, parent, length):
            if not node: 
                return
            if parent and node.val == parent.val + 1:
                length += 1
            else:
                length = 1
            self.ans = max(self.ans, length)
            detect(node.right, node, length)
            detect(node.left, node, length)
        
        detect(root, None, 0)
        return self.ans

Bottom-Up

class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        def detect(node):
            if not node:
                return 0
            
            l = detect(node.left) + 1
            r = detect(node.right) + 1
            if node.left and node.val + 1 != node.left.val:
                l = 1
            if node.right and node.val + 1 != node.right.val:
                r = 1
            
            length = max(l, r)
            self.ans = max(self.ans, length)
            return length
        
        self.ans = 0
        detect(root)
        return self.ans