ಬೈನರಿ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಉತ್ತಮ ನೋಡ್‌ಗಳನ್ನು ಎಣಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಮೈಕ್ರೋಸಾಫ್ಟ್
ಬೈನರಿ ಟ್ರೀ ಆಳದ ಮೊದಲ ಹುಡುಕಾಟ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ ಎ ಬೈನರಿ ಮರ ಅದರ ಮೂಲದೊಂದಿಗೆ ನೀಡಲಾಗಿದೆ. ಮೂಲದಿಂದ X ಗೆ ಹೋಗುವ ಹಾದಿಯಲ್ಲಿ X ಗಿಂತ ಹೆಚ್ಚಿನ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ನೋಡ್‌ಗಳಿಲ್ಲದಿದ್ದರೆ ಮರದಲ್ಲಿನ ನೋಡ್ X ಅನ್ನು ಉತ್ತಮ ಎಂದು ಹೆಸರಿಸಲಾಗಿದೆ.

ಕೊಟ್ಟಿರುವ ಬೈನರಿ ಮರದಲ್ಲಿನ ಉತ್ತಮ ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಾವು ಹಿಂದಿರುಗಿಸಬೇಕಾಗಿದೆ.

ಉದಾಹರಣೆ

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

ವಿವರಣೆ:

ಬೈನರಿ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಉತ್ತಮ ನೋಡ್‌ಗಳನ್ನು ಎಣಿಸಿ

ನೀಲಿ ಬಣ್ಣದಲ್ಲಿರುವ ನೋಡ್‌ಗಳು ಉತ್ತಮವಾಗಿವೆ.
ರೂಟ್ ನೋಡ್ (3) ಯಾವಾಗಲೂ ಉತ್ತಮ ನೋಡ್ ಆಗಿದೆ.
ನೋಡ್ 4 -> (3,4) ಎಂಬುದು ಮೂಲದಿಂದ ಪ್ರಾರಂಭವಾಗುವ ಹಾದಿಯಲ್ಲಿನ ಗರಿಷ್ಠ ಮೌಲ್ಯವಾಗಿದೆ.
ನೋಡ್ 5 -> (3,4,5) ಎಂಬುದು ಮಾರ್ಗದಲ್ಲಿನ ಗರಿಷ್ಠ ಮೌಲ್ಯವಾಗಿದೆ
ಮತ್ತು ನೋಡ್ 3 -> (3,1,3) ಎಂಬುದು ಮಾರ್ಗದಲ್ಲಿನ ಗರಿಷ್ಠ ಮೌಲ್ಯವಾಗಿದೆ.

    3
   /
  3
 / \
4   2
3

ವಿವರಣೆ:

ಬೈನರಿ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಉತ್ತಮ ನೋಡ್‌ಗಳನ್ನು ಎಣಿಸಿ

ನೋಡ್ 2 -> (3, 3, 2) ಉತ್ತಮವಾಗಿಲ್ಲ, ಏಕೆಂದರೆ “3” ಅದಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿದೆ.

ಅಪ್ರೋಚ್

ನೋಡ್ ಉತ್ತಮವಾಗಿದೆಯೆ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಮೂಲದಿಂದ ಆ ನೋಡ್‌ಗೆ ಹೋಗಬೇಕು ಮತ್ತು ಈ ಮಾರ್ಗದಲ್ಲಿ ಅದರ ಮೌಲ್ಯವು ಗರಿಷ್ಠಕ್ಕಿಂತ ಚಿಕ್ಕದಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಬೇಕು.
ಉತ್ತಮ ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಕೊಟ್ಟಿರುವ ಬೈನರಿ ಮರದ ಪ್ರತಿಯೊಂದು ನೋಡ್‌ಗೆ ಈ ರೀತಿ ಪರಿಶೀಲಿಸಬೇಕು. ಆದರೆ ಇಲ್ಲಿ ಒಂದು ವಿಷಯವನ್ನು ಗಮನಿಸಿ,

ಒಂದು ನಿರ್ದಿಷ್ಟ ನೋಡ್‌ಗೆ ಅದರ ಮಾರ್ಗವನ್ನು ಮೂಲದಿಂದ ಹಾದುಹೋಗುವ ಮೂಲಕ ನಾವು ಉತ್ತರವನ್ನು ಕಂಡುಕೊಂಡರೆ, ನಾವು ಅಲ್ಲಿಂದಲೇ ಅದರ ಮಕ್ಕಳ ನೋಡ್‌ಗೆ ಹೋಗಬಹುದು ಏಕೆಂದರೆ ನಾವು ಈಗಾಗಲೇ ಮಕ್ಕಳ ನೋಡ್‌ನ ಬಹುತೇಕ ಹಾದಿಯನ್ನು ದಾಟಿದ್ದೇವೆ ಮತ್ತು ನಾವು ಇನ್ನೂ ಗರಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ಇನ್ನೂ ಹೊಂದಿದ್ದೇವೆ. ಅದರ ಎರಡೂ ಮಕ್ಕಳ ನೋಡ್‌ಗೆ ವರ್ಗಾಯಿಸಲು ನಾವು ಪ್ರಸ್ತುತ ನೋಡ್ ಮೌಲ್ಯದೊಂದಿಗೆ ಗರಿಷ್ಠವನ್ನು ನವೀಕರಿಸಬೇಕಾಗಿದೆ.
ಆದ್ದರಿಂದ ಇದು ಡಿಎಫ್‌ಎಸ್ ಅಥವಾ ಪುನರಾವರ್ತನೆಯಂತೆ ಕಾಣುತ್ತದೆ, ನಿರ್ದಿಷ್ಟ ನೋಡ್‌ಗೆ ಎಲ್ಲಿಗೆ ಹೋಗಬೇಕು ಎಂದು ನಾವು ಮೂಲದಿಂದ ಆ ನೋಡ್‌ಗೆ ಹೋಗುತ್ತೇವೆ. ಆದ್ದರಿಂದ ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ ಪುನರಾವರ್ತನೆ ಬಹಳ ಸಹಾಯಕವಾಗುತ್ತದೆ. ಹಂತಗಳು ಹೀಗಿವೆ:

  • ಅದರ ನಿಯತಾಂಕವಾಗಿ ಎರಡು ವಾದಗಳೊಂದಿಗೆ ಪುನರಾವರ್ತಿತ ಕಾರ್ಯವನ್ನು ರಚಿಸಿ. ಒಂದು ನೋಡ್ನ ವಿಳಾಸ ಮತ್ತು ಎರಡನೆಯದು ನಾವು ಇಲ್ಲಿಯವರೆಗೆ ಕಂಡುಕೊಂಡ ಗರಿಷ್ಠ ಮೌಲ್ಯ.
  • ಈಗ ನಾವು ನಿರ್ದಿಷ್ಟ ನೋಡ್‌ನಲ್ಲಿರುವಾಗಲೆಲ್ಲಾ ಪ್ರಸ್ತುತ ನೋಡ್ ಮೌಲ್ಯವು ಪ್ರಸ್ತುತ ಗರಿಷ್ಠಕ್ಕಿಂತ ಚಿಕ್ಕದಾಗಿದೆ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅದು ಚಿಕ್ಕದಾಗದಿದ್ದರೆ ನಾವು ಈ ನೋಡ್ ಅನ್ನು ನಮ್ಮ ಉತ್ತರಕ್ಕೆ ಸೇರಿಸುತ್ತೇವೆ ಮತ್ತು ಗರಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ನವೀಕರಿಸಿದ ನಂತರ ಅದರ ಮಕ್ಕಳ ನೋಡ್‌ಗಳಿಗೆ ಅದೇ ಕಾರ್ಯವನ್ನು ಕರೆಯುತ್ತೇವೆ.

ಅನುಷ್ಠಾನ

ಬೈನರಿ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಉತ್ತಮ ನೋಡ್‌ಗಳನ್ನು ಎಣಿಸಲು ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಬೈನರಿ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಉತ್ತಮ ನೋಡ್‌ಗಳನ್ನು ಎಣಿಸುವ ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

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

ಬೈನರಿ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಉತ್ತಮ ನೋಡ್‌ಗಳನ್ನು ಎಣಿಸಲು ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್): ಇಲ್ಲಿ n ಎಂಬುದು ಕೊಟ್ಟಿರುವ ಬೈನರಿ ಮರದಲ್ಲಿನ ಒಟ್ಟು ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆ. ನಾವು ಪ್ರತಿ ನೋಡ್‌ಗೆ ಒಮ್ಮೆ ಭೇಟಿ ನೀಡುತ್ತಿದ್ದೇವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (ಎನ್): ಬಳಸಿದ ಸ್ಥಳವು ಪುನರಾವರ್ತಿತ ಸ್ಟ್ಯಾಕ್‌ನ ಗರಿಷ್ಠ ಗಾತ್ರವಾಗಿರುತ್ತದೆ. ಕೆಟ್ಟದಾಗಿ ಅದು ಓರೆಯಾದ ಬೈನರಿ ಮರದ ಸಂದರ್ಭದಲ್ಲಿ O (n) ಗಾತ್ರಕ್ಕೆ ಹೋಗಬಹುದು.