[LeetCode] 298. Binary Tree Longest Consecutive Sequence

3957 단어
두 갈래 나무의 최장 연속 서열.제목은 두 갈래 나무에 가장 긴 연속 서열을 구하는 것이다.예는 다음과 같다.
Example 1: 
Input:

   1
    \
     3
    / \
   2   4
        \
         5

Output: 3

Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2: 
Input:

   2
    \
     3
    / 
   2    
  / 
 1

Output: 2 

Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

이 문제는 제가 DFS의 해법을 제시합니다. 마찬가지로 먼저 반복합니다.
시간 O(n)
공간 O(n)
 1 /**
 2  * Definition for a binary tree node.
 3  * function TreeNode(val) {
 4  *     this.val = val;
 5  *     this.left = this.right = null;
 6  * }
 7  */
 8 /**
 9  * @param {TreeNode} root
10  * @return {number}
11  */
12 var longestConsecutive = function(root) {
13     return helper(root);
14 };
15 
16 var helper = function(node, prev, count) {
17     if (!node) {
18         return count || 0;
19     }
20     if (node.val === prev + 1) {
21         count++;
22     } else {
23         count = 1;
24     }
25     let res = Math.max(
26         count,
27         helper(node.left, node.val, count),
28         helper(node.right, node.val, count)
29     );
30     return res;
31 };
이미 알고 있는 후순에서 선순을 구합니다 (이차 트리)
SwiftUI 프로젝트에 Apple로 로그인을 추가하는 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage