ಬೈನರಿ ಟ್ರೀನಲ್ಲಿ ಗರಿಷ್ಠ ಮಟ್ಟದ ಮೊತ್ತವನ್ನು ಹುಡುಕಿ


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

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

“ಬೈನರಿ ಟ್ರೀನಲ್ಲಿ ಗರಿಷ್ಠ ಮಟ್ಟದ ಮೊತ್ತವನ್ನು ಹುಡುಕಿ” ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಬೈನರಿ ಮರ ಧನಾತ್ಮಕ ಮತ್ತು negative ಣಾತ್ಮಕ ನೋಡ್‌ಗಳೊಂದಿಗೆ, ಬೈನರಿ ಮರದಲ್ಲಿ ಒಂದು ಹಂತದ ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ಹುಡುಕಿ.

ಉದಾಹರಣೆ

ಇನ್ಪುಟ್
ಬೈನರಿ ಟ್ರೀನಲ್ಲಿ ಗರಿಷ್ಠ ಮಟ್ಟದ ಮೊತ್ತವನ್ನು ಹುಡುಕಿ

7

ವಿವರಣೆ
ಮೊದಲ ಹಂತ: ಮೊತ್ತ = 5
ಎರಡನೇ ಹಂತ: ಮೊತ್ತ = (-2 + 6) = 4
ಮೂರನೇ ಹಂತ: ಮೊತ್ತ = (11 + (-5) + 1) = 7
ನಾಲ್ಕನೇ ಹಂತ: ಮೊತ್ತ = (3 + (-3)) = 0
ಗರಿಷ್ಠ ಮೊತ್ತ = 7

ಬೈನರಿ ಟ್ರೀನಲ್ಲಿ ಗರಿಷ್ಠ ಮಟ್ಟದ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಅಲ್ಗಾರಿದಮ್

ಲೆವೆಲ್ ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಮಾಡುವುದು ಮತ್ತು ಪ್ರತಿ ಹಂತಕ್ಕೂ ಆ ಹಂತದ ಎಲ್ಲಾ ನೋಡ್‌ಗಳ ಮೊತ್ತವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವುದು ಇದರ ಆಲೋಚನೆ. ಮೊತ್ತವು ಗರಿಷ್ಠ ಮೊತ್ತಕ್ಕಿಂತ ಹೆಚ್ಚಿದ್ದರೆ, ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ನವೀಕರಿಸಿ.

  1. ಒಂದು ರಚಿಸಿ ಕ್ಯೂ, ಮತ್ತು ರೂಟ್ ನೋಡ್ ಅನ್ನು ಸರದಿಗೆ ತಳ್ಳಿರಿ. ವೇರಿಯಬಲ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ maxSum ನಕಾರಾತ್ಮಕ ಅನಂತವಾಗಿ.
  2. ಕ್ಯೂ ಖಾಲಿಯಾಗಿಲ್ಲದಿದ್ದರೂ ಹಂತ 3 ಮತ್ತು 4 ಅನ್ನು ಪುನರಾವರ್ತಿಸಿ.
  3. ಈ ಕ್ಷಣದಲ್ಲಿ ಒಂದು ಹಂತವು ಸರದಿಯಲ್ಲಿದೆ. ಹೆಸರಿನ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ ಗಾತ್ರ ಕ್ಯೂನ ಗಾತ್ರ ಮತ್ತು ವೇರಿಯಬಲ್ ಮೊತ್ತವನ್ನು 0 ಎಂದು.
  4. I = 0 ರಿಂದ ಗಾತ್ರಕ್ಕೆ ಒಂದು ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ, ಮತ್ತು ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ ಕ್ಯೂನಿಂದ ಒಂದು ಅಂಶವನ್ನು ಪಾಪ್ out ಟ್ ಮಾಡಿ. ಈ ಅಂಶದ ಮೌಲ್ಯವನ್ನು ವೇರಿಯಬಲ್ ಮೊತ್ತಕ್ಕೆ ಸೇರಿಸಿ ಮತ್ತು ಪಾಪ್ out ಟ್ ನೋಡ್‌ನ ಮಕ್ಕಳನ್ನು ಸರದಿಗೆ ತಳ್ಳಿರಿ. ಮೊತ್ತವು ಮ್ಯಾಕ್ಸ್‌ಸಮ್‌ಗಿಂತ ಹೆಚ್ಚಿದ್ದರೆ ಲೂಪ್‌ನ ಕೊನೆಯಲ್ಲಿ, ಮ್ಯಾಕ್ಸ್‌ಸಮ್ ಅನ್ನು ಮೊತ್ತವಾಗಿ ನವೀಕರಿಸಿ.
  5. ಮ್ಯಾಕ್ಸ್‌ಸಮ್ ಹಿಂತಿರುಗಿ.

ವಿವರಣೆ

ಮೇಲಿನ ಉದಾಹರಣೆಯಲ್ಲಿ ಮರವನ್ನು ಪರಿಗಣಿಸಿ

ಹಂತ 1

ಕ್ಯೂ ರಚಿಸಿ ಮತ್ತು ಅದಕ್ಕೆ ಮೂಲವನ್ನು ತಳ್ಳಿರಿ. Negative ಣಾತ್ಮಕ ಅನಂತತೆಯಂತೆ ವೇರಿಯೇಬಲ್ ಮ್ಯಾಕ್ಸ್‌ಸಮ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ.
ಕ್ಯೂ = 5 ಮತ್ತು ಮ್ಯಾಕ್ಸ್‌ಸಮ್ = -ಇನ್‌ಫಿನಿಟಿ

ಹಂತ 2

ಕ್ಯೂ ಖಾಲಿಯಾಗಿಲ್ಲದಿದ್ದರೂ ಹಂತ 3 ಮತ್ತು 4 ಅನ್ನು ಪುನರಾವರ್ತಿಸಿ.

ಹಂತ 3 ಮತ್ತು 4

ಪುನರಾವರ್ತನೆ 1
ಗಾತ್ರ = 1, ಮೊತ್ತ = 0
ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಕ್ಯೂನಿಂದ ತೆಗೆದುಹಾಕಿ, ಪ್ರತಿ ಅಂಶದ ಮೌಲ್ಯವನ್ನು ಮೊತ್ತಕ್ಕೆ ಸೇರಿಸಿ ಮತ್ತು ಪ್ರತಿ ಅಂಶದ ಮಕ್ಕಳನ್ನು ಸರದಿಗೆ ತಳ್ಳಿರಿ.
ಮೊತ್ತ = 5, ಕ್ಯೂ = -2 -> 6
ಮ್ಯಾಕ್ಸ್‌ಸಮ್ ಅನ್ನು ನವೀಕರಿಸಿ, ಆದ್ದರಿಂದ, ಮ್ಯಾಕ್ಸ್‌ಸಮ್ = 5

ಪುನರಾವರ್ತನೆ 2
ಗಾತ್ರ = 2, ಮೊತ್ತ = 0
ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಕ್ಯೂನಿಂದ ತೆಗೆದುಹಾಕಿ, ಪ್ರತಿ ಅಂಶದ ಮೌಲ್ಯವನ್ನು ಮೊತ್ತಕ್ಕೆ ಸೇರಿಸಿ ಮತ್ತು ಪ್ರತಿ ಅಂಶದ ಮಕ್ಕಳನ್ನು ಸರದಿಗೆ ತಳ್ಳಿರಿ.
sum = (-2 + 6) = 4, ಕ್ಯೂ = 11 -> -5 -> 1
ಮ್ಯಾಕ್ಸ್‌ಸಮ್ ಅನ್ನು ನವೀಕರಿಸಿ, ಆದ್ದರಿಂದ, ಮ್ಯಾಕ್ಸ್‌ಸಮ್ = 5

ಪುನರಾವರ್ತನೆ 3
ಗಾತ್ರ = 3, ಮೊತ್ತ = 0
ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಕ್ಯೂನಿಂದ ತೆಗೆದುಹಾಕಿ, ಪ್ರತಿ ಅಂಶದ ಮೌಲ್ಯವನ್ನು ಮೊತ್ತಕ್ಕೆ ಸೇರಿಸಿ ಮತ್ತು ಪ್ರತಿ ಅಂಶದ ಮಕ್ಕಳನ್ನು ಸರದಿಗೆ ತಳ್ಳಿರಿ.
ಮೊತ್ತ = (11 + (-5) + 1) = 7, ಕ್ಯೂ = 3 -> -3
ಮ್ಯಾಕ್ಸ್‌ಸಮ್ ಅನ್ನು ನವೀಕರಿಸಿ, ಆದ್ದರಿಂದ, ಮ್ಯಾಕ್ಸ್‌ಸಮ್ = 7

ಪುನರಾವರ್ತನೆ 4
ಗಾತ್ರ = 2, ಮೊತ್ತ = 0
ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಕ್ಯೂನಿಂದ ತೆಗೆದುಹಾಕಿ, ಪ್ರತಿ ಅಂಶದ ಮೌಲ್ಯವನ್ನು ಮೊತ್ತಕ್ಕೆ ಸೇರಿಸಿ ಮತ್ತು ಪ್ರತಿ ಅಂಶದ ಮಕ್ಕಳನ್ನು ಸರದಿಗೆ ತಳ್ಳಿರಿ.
ಮೊತ್ತ = (3 + (-3)) = 0, ಕ್ಯೂ = ಶೂನ್ಯ
ಮ್ಯಾಕ್ಸ್‌ಸಮ್ ಅನ್ನು ನವೀಕರಿಸಿ, ಆದ್ದರಿಂದ, ಮ್ಯಾಕ್ಸ್‌ಸಮ್ = 7

ಕ್ಯೂ ಖಾಲಿಯಾಗುವುದರಿಂದ ನಾವು ನಿಲ್ಲಿಸುತ್ತೇವೆ ಮತ್ತು ಒಂದು ಹಂತದ ಗರಿಷ್ಠ ಮೊತ್ತ 7 ಆಗಿದೆ.

ಕೋಡ್

ಬೈನರಿ ಟ್ರೀನಲ್ಲಿ ಗರಿಷ್ಠ ಮಟ್ಟದ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

import java.util.LinkedList;
import java.util.Queue;

class FindMaximumLevelSumInBinaryTree {
    // class representing node of binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int maxLevelSum(Node root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }       
        // create a queue and push root to it
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        // initialize maxSum as negative infinity 
        int maxSum = Integer.MIN_VALUE;
        
        // while queue is not empty
        while (!queue.isEmpty()) {
            // At this moment the queue contains one level in it
            // initialize size as size of queue
            int size = queue.size();
            // initialize sum as 0, this represents the sum of a level
            int sum = 0;
            // run a loop from 0 to size
            for (int i = 0; i < size; i++) {
                // remove an element from queue
                Node curr = queue.poll();
                // add the value of current element to sum
                sum += curr.data;
                
                // push the children of current element to queue
                if (curr.left != null)
                    queue.add(curr.left);
                
                if (curr.right != null)
                    queue.add(curr.right);
            }

            // update max sum
            maxSum = Math.max(maxSum, sum);
        }
        
        // return max sum
        return maxSum;
    }

    public static void main(String[] args) {
        // Example tree
        Node root = new Node(5);
        root.left = new Node(-2);
        root.right = new Node(6);
        root.left.left = new Node(11);
        root.right.left = new Node(-5);
        root.right.right = new Node(1);
        root.right.right.left = new Node(3);
        root.right.right.right = new Node(-3);

        System.out.println(maxLevelSum(root));
    }
}
7

ಬೈನರಿ ಟ್ರೀನಲ್ಲಿ ಗರಿಷ್ಠ ಮಟ್ಟದ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

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

// class representing node of a binary tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node with data d
Node* newNode(int d) {
    Node *node = new Node(d);
    return node;
}

int maxLevelSum(Node *root) {
    if (root == NULL) {
        return INT_MIN;
    }
    
    // create a queue and push root to it
    queue<Node*> q;
    q.push(root);
    // initialize maxSum as negative infinity
    int maxSum = INT_MIN;
    
    // while queue is not empty
    while (!q.empty()) {
        // At this moment the queue contains one level in it
        // initialize size as size of queue
        int size = q.size();
        // initialize sum as 0, this represents the sum of a level
        int sum = 0;
        
        // run a loop from 0 to size
        for (int i = 0; i < size; i++) {
            // remove an element from queue
            Node *curr = q.front();
            q.pop();
            // add the value of current element to sum
            sum += curr->data;
            
            // push the children of current element to queue
            if (curr->left != NULL)
                q.push(curr->left);
                
            if (curr->right != NULL)
                q.push(curr->right);
        }
        
        // update max sum
        maxSum = std::max(maxSum, sum);
    }
    
    // return max sum
    return maxSum;
}

int main() {
    // Example tree
    Node *root = newNode(5);
    root->left = newNode(-2);
    root->right = newNode(6);
    root->left->left = newNode(11);
    root->right->left = newNode(-5);
    root->right->right = newNode(1);
    root->right->right->left = newNode(3);
    root->right->right->right = newNode(-3);
    
    cout<<maxLevelSum(root)<<endl;
    
    return 0;
}
7

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಎಲ್ಲಾ ಮರದ ಅಂಶಗಳ ಮೇಲೆ ಸುಮ್ಮನೆ ಸಂಚರಿಸುತ್ತೇವೆ ಮತ್ತು ಅವುಗಳನ್ನು ಎರಡು ಬಾರಿ ಸರದಿಯಲ್ಲಿ ತಳ್ಳುತ್ತೇವೆ. ಆದ್ದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

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

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಪ್ರತಿ ಹಂತದ ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಕ್ಯೂ ಬಳಸಿದ್ದೇವೆ. ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯೂ ರೇಖೀಯವಾಗಿದೆ.