Hər Ağac Satırında Ən Böyük Dəyəri tapın LeetCode Həll

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Facebook LinkedIn SamsungBaxılıb 21

Problem bəyanat

Hər Ağac Satırında Ən Böyük Dəyəri Tapın LeetCode Həlli – Nəzərə alınmaqla root ikili ağacın qaytarılması hər sətirdə ən böyük dəyərə malik massiv ağacın (0 indeksli).

misal

Test işi 1:

Input:

kök = [1, 3, 4, 5, 3, null, 9]

Çıxış:

[1, 3, 9]

Hər Ağac Satırında Ən Böyük Dəyəri tapın LeetCode HəllPin

Izahat

1, 3 və 9 müvafiq sıralarındakı ən böyük dəyərlərdir.

Yanaşma:

Burada hər bir sətirdə, yəni hər səviyyədə maksimum dəyər lazımdır. Beləliklə, biz, əsasən, səviyyəyə görə səviyyəli sifariş keçidini edə bilərik və maksimum dəyəri izləyə bilərik. Beləliklə, əsasən edirik BFS burada. Səviyyəni və nömrəni izləyərkən BFS-də ağacı keçməliyik. səviyyədə qovşaqların. BFS-də hər iterasiyadan sonra Növbəyə baxsaq, o, həmişə səviyyədə elementlərin dəqiq miqdarını ehtiva edir. belə yox. həmin səviyyədəki elementlərin sayı növbənin ölçüsünə bərabərdir, biz etməli olduğumuz yeganə şey həmin səviyyədə/iterasiyada maxValue-ni izləməkdir.

Amma biz də edə bilərik DFS problemi həll etmək üçün burada. DFS dərinlikdən birinci şəkildə hərəkət edir, ona görə də keçid zamanı biz həmin səviyyədə səviyyəni və maxValue-ni izləməli və onu massivin müvafiq səviyyə indeksində saxlamalıyıq. Burada biz hər qovşaqda massiv qururuq, yəni çıxış massivindəki dəyəri yeniləməli və ya çıxış massivinə yeni dəyər əlavə etməli olduğumuza qərar verməliyik.

Hər Ağac Satırında Ən Böyük Dəyəri Tapmaq üçün Kod

Java Proqramı

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> maxValues = new ArrayList<>();
        if(root == null) return maxValues;
        
        Queue<TreeNode> bfs = new LinkedList<>();
        bfs.offer(root);
        
        while(!bfs.isEmpty()){
            int size = bfs.size();
            int count = 0;
            int max = Integer.MIN_VALUE;
      
      // check all the elements in the current level;
            while(count < size){
                TreeNode curr = bfs.poll();
                
        // get the max value
                max = Math.max(max, curr.val);
                
                if(curr.left != null){
                    bfs.offer(curr.left);
                }
                
                if(curr.right != null){
                    bfs.offer(curr.right);
                }
                
                count++;
            }
            
      // store it in the output.
            maxValues.add(max);
        }
        
        return maxValues;
    }
}

C ++ Proqramı

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        if(root == NULL)
            return result;
        queue<TreeNode*> q;
        q.push(root);
        int maxVal = INT_MIN;
        
        while(!q.empty()){
            int len = q.size();
            maxVal = INT_MIN;
            for(int idx = 0; idx < len; idx++){
                TreeNode* front = q.front();
                q.pop();
                if(front->val > maxVal){
                    maxVal = front->val;
                }
                
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            
            result.push_back(maxVal);
        }
        
        return result;
    }
};

Hər Ağac Satırında Ən Böyük Dəyəri Tapmaq üçün Mürəkkəblik Təhlili LeetCode Həll

Zaman Mürəkkəbliyi: O (n) — Hər qovşağına bir dəfə toxunuruq
Kosmik Mürəkkəblik: O (n) — Tam və tamın son səviyyəsi ikili ağac N/2 qovşaqları ola bilər. Növbə hər səviyyəni saxlayır.

Translate »