이진 트리 Leetcode 솔루션에서 좋은 노드 계산

난이도 중급
자주 묻는 질문 아마존 Microsoft
알고리즘 이진 트리 코딩 깊이 우선 검색 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 29

문제 정책

이 문제에서 이진 트리 뿌리와 함께 주어집니다. 루트에서 X까지의 경로에 X보다 큰 값을 가진 노드가 없으면 트리에서 노드 X의 이름이 good으로 지정됩니다.

주어진 이진 트리에서 좋은 노드의 수를 반환해야합니다.

    3
   / \
  1   4
 /   / \
3   1   5
4

설명 :

이진 트리 Leetcode 솔루션에서 좋은 노드 계산

파란색 노드가 좋습니다.
루트 노드 (3)는 항상 좋은 노드입니다.
노드 4-> (3,4)는 루트에서 시작하는 경로의 최대 값입니다.
노드 5-> (3,4,5)는 경로의 최대 값입니다.
그리고 노드 3-> (3,1,3)은 경로의 최대 값입니다.

    3
   /
  3
 / \
4   2
3

설명 :

이진 트리 Leetcode 솔루션에서 좋은 노드 계산

노드 2-> (3, 3, 2)는“3”이 그것보다 높기 때문에 좋지 않습니다.

접근

노드가 양호한 지 여부를 확인하려면 루트에서 해당 노드로 경로를 탐색하고 해당 값이이 경로에서 최대 값보다 작지 않은지 확인해야합니다.
좋은 노드의 수를 찾으려면 주어진 이진 트리의 각 노드에 대해 이와 같이 확인해야합니다. 하지만 여기서 한 가지를 살펴보세요.

루트에서 경로를 탐색하여 특정 노드에 대한 답을 찾으면 하위 노드의 거의 경로도 이미 탐색했으며 아직까지 탐색 된 최대 값이 있기 때문에 거기에서 자식 노드로도 이동할 수 있습니다. 현재 노드 값으로 최대 값을 업데이트하여 두 하위 노드로 전송하면됩니다.
따라서 이것은 루트에서 해당 노드로의 경로를 횡단하는 특정 노드로 이동하는 DFS 또는 재귀처럼 보입니다. 따라서이 문제에서 재귀는 매우 도움이 될 것입니다. 단계는 다음과 같습니다.

  • 두 개의 인수를 매개 변수로 사용하여 재귀 함수를 만듭니다. 하나는 노드의 주소이고 두 번째는 여기까지 찾은 최대 값입니다.
  • 이제 특정 노드에있을 때마다 현재 노드 값이 현재 최대 값보다 작은 지 확인합니다. 더 작지 않은 경우이 노드를 ans에 추가하고 최대 값을 업데이트 한 후 자식 노드에 대해 동일한 함수를 호출합니다.

실시

이진 트리 Leetcode 솔루션에서 Count Good 노드를위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left,*right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int rec(TreeNode* root, int mx)
{
   if(!root) return 0;

    int cur=0;
    if(mx <= root->val) cur++;

    mx=max(mx,root->val);
    return rec(root->left,mx) + rec(root->right,mx) + cur;
}

int goodNodes(TreeNode* root) {

    int mx= INT_MIN;
    return rec(root,mx);
}

int main() 
{
    TreeNode* root= new TreeNode(3);
    root->left=  new TreeNode(1);
    root->right=  new TreeNode(4);
    root->left->left=  new TreeNode(3);
    root->right->left=  new TreeNode(1);
    root->right->right=  new TreeNode(5);
    
    cout<< goodNodes(root) ;
    return 0; 
}
4

이진 트리 Leetcode 솔루션에서 Count Good 노드를위한 Java 프로그램

class Rextester{
    
static class TreeNode {
    int val;
    TreeNode left,right;
    TreeNode(int x)  {
        val=x;
        left=null;
        right=null;
    }
}
    
    static int rec(TreeNode root, int mx)
    {
        if(root==null) return 0;
        
        int cur=0;
        if(mx <= root.val) cur++;
        
        mx = Math.max(mx,root.val);
        return rec(root.left,mx) + rec(root.right,mx) + cur;
    }
    
    public static int goodNodes(TreeNode root) 
    {     
        int mx= Integer.MIN_VALUE;
        return rec(root,mx);       
    }
    
  public static void main(String args[])
    {
        TreeNode root= new TreeNode(3);
        root.left=  new TreeNode(1);
        root.right=  new TreeNode(4);
        root.left.left=  new TreeNode(3);
        root.right.left=  new TreeNode(1);
        root.right.right=  new TreeNode(5);
        
        System.out.println( goodNodes(root) );
    }
}
4

이진 트리 Leetcode 솔루션의 Count Good 노드에 대한 복잡성 분석

시간 복잡성

의 위에) : 여기서 n은 주어진 이진 트리의 총 노드 수입니다. 우리는 각 노드를 한 번 방문합니다.

공간 복잡성 

의 위에) : 사용 된 공간은 재귀 스택의 최대 크기입니다. 최악의 경우 왜곡 된 이진 트리의 경우 O (n) 크기로 갈 수 있습니다.

코멘트를 남겨

Translate »
1