ਬਾਈਨਰੀ ਟਰੀ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿੱਚ ਚੰਗੇ ਨੋਡ ਗਿਣੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ Microsoft ਦੇ
ਬਾਈਨਰੀ ਟਰੀ ਡੂੰਘਾਈ ਪਹਿਲੀ ਖੋਜ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਇਸ ਸਮੱਸਿਆ ਵਿਚ ਏ ਬਾਈਨਰੀ ਟਰੀ ਇਸ ਦੀ ਜੜ੍ਹ ਦੇ ਨਾਲ ਦਿੱਤਾ ਗਿਆ ਹੈ. ਦਰੱਖਤ ਵਿਚ ਇਕ ਨੋਡ ਐਕਸ ਦਾ ਨਾਮ ਵਧੀਆ ਰੱਖਿਆ ਗਿਆ ਹੈ ਜੇ ਰੂਟ ਤੋਂ ਐਕਸ ਤੱਕ ਦੇ ਰਸਤੇ ਵਿਚ ਐਕਸ ਨਾਲੋਂ ਵੱਡਾ ਮੁੱਲ ਵਾਲਾ ਕੋਈ ਨੋਡ ਨਹੀਂ ਹੁੰਦਾ.

ਸਾਨੂੰ ਦਿੱਤੇ ਗਏ ਬਾਈਨਰੀ ਟ੍ਰੀ ਵਿਚ ਚੰਗੇ ਨੋਡਾਂ ਦੀ ਗਿਣਤੀ ਵਾਪਸ ਕਰਨੀ ਹੈ.

ਉਦਾਹਰਨ

    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

ਬਾਇਨਰੀ ਟਰੀ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿੱਚ ਕਾਉਂਟ ਗੁੱਡ ਨੋਡਜ਼ ਲਈ ਪੇਚੀਦਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ): ਜਿੱਥੇ ਕਿ ਦਿੱਤੇ ਗਏ ਬਾਈਨਰੀ ਟਰੀ ਵਿਚ ਨੋਡਾਂ ਦੀ ਕੁੱਲ ਸੰਖਿਆ ਹੈ. ਅਸੀਂ ਹਰੇਕ ਨੋਡ ਨੂੰ ਇਕ ਵਾਰ ਵੇਖ ਰਹੇ ਹਾਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ 

ਓ (ਐਨ): ਵਰਤੀ ਗਈ ਸਪੇਸ ਦੁਹਰਾਉਣ ਵਾਲੇ ਸਟੈਕ ਦਾ ਅਧਿਕਤਮ ਅਕਾਰ ਹੋਵੇਗੀ. ਘਟੀਆ ਬਾਈਨਰੀ ਟਰੀ ਦੇ ਮਾਮਲੇ ਵਿਚ ਇਹ ਸਭ ਤੋਂ ਵੱਧ (ਓ) ਆਕਾਰ ਤੇ ਜਾ ਸਕਦਾ ਹੈ.