Binary Tree Ziqzaq Səviyyəsi Sifarişin Keçməsi LeetCode Həlli


Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Cisco DocuSign eBay Facebook Flipkart GoDaddy Goldman Sachs google LinkedIn microsoft Kahin Paytm Salesforce Samsung SAP XidmətNow Über VMwareBaxılıb 78

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Binary Tree Ziqzaq Səviyyəsi Sifarişin Keçməsi LeetCode Həlli – Nəzərə alınmaqla root ikili ağacın qaytarılması onun qovşaqlarının dəyərlərinin ziqzaq səviyyəsi üçün keçidi. (yəni, növbəti səviyyə üçün soldan sağa, sonra sağdan sola və alternativ olaraq).

Binary Tree Ziqzaq Səviyyəsi Sifarişin Keçməsi LeetCode HəlliPin

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Izahat

Biz sadə həyata keçiririk səviyyəli nizamlı lakin ans-a əlavə etməzdən əvvəl alternativ səviyyələri tərsinə çevirin.

Bu problemdə biz ikili ağac səviyyəsini səviyyə ilə keçməliyik. İkili ağacda səviyyələri görəndə, düşünməliyik BFS, çünki bu, onun məntiqidir: biz daha dərinə getməzdən əvvəl ilk növbədə bütün qonşuları keçib gedir. Burada da hər səviyyədə istiqaməti dəyişdirməliyik. Beləliklə, alqoritm aşağıdakı kimidir:

  1. Biz yaradırıq queue, kökümüzü ilk qoyduğumuz yer.
  2. result son nəticəni saxlamaqdır və direction, bərabərdir 1 or -1 ya da biz onu travers istiqamətində boolean kimi saxlaya bilərik.
  3. Sonra səviyyədən səviyyəyə keçməyə başlayırıq: əgər varsa k Hal-hazırda növbədə olan elementlər, biz onların hamısını çıxarırıq və yerinə uşaqlarını qoyuruq. Növbəmiz boş olana qədər bunu etməyə davam edirik. Bu arada biz formalaşdırırıq level siyahısı və sonra əlavə edin result, düzgün istiqamətdə istifadə və sonra istiqaməti dəyişdirmək.

Kodu

İkili Ağac Ziqzaq Səviyyə Sifarişi üçün C++ Kodu

class Solution {
public:
   vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
    if (root == NULL) {
        return vector<vector<int> > ();
    }
    vector<vector<int> > result;

    queue<TreeNode*> nodesQueue;
    nodesQueue.push(root);
    bool leftToRight = true;

    while ( !nodesQueue.empty()) {
        int size = nodesQueue.size();
        vector<int> row(size);
        for (int i = 0; i < size; i++) {
            TreeNode* node = nodesQueue.front();
            nodesQueue.pop();

            // find position to fill node's value
            int index = (leftToRight) ? i : (size - 1 - i);

            row[index] = node->val;
            if (node->left) {
                nodesQueue.push(node->left);
            }
            if (node->right) {
                nodesQueue.push(node->right);
            }
        }
        // after this level
        leftToRight = !leftToRight;
        result.push_back(row);
    }
    return result;
}
};

Binary Tree Ziqzaq Səviyyə Sifarişi üçün Java Kodu

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
    {
        List<List<Integer>> sol = new ArrayList<>();
        travel(root, sol, 0);
        return sol;
    }
    
    private void travel(TreeNode curr, List<List<Integer>> sol, int level)
    {
        if(curr == null) return;
        
        if(sol.size() <= level)
        {
            List<Integer> newLevel = new LinkedList<>();
            sol.add(newLevel);
        }
        
        List<Integer> collection  = sol.get(level);
        if(level % 2 == 0) collection.add(curr.val);
        else collection.add(0, curr.val);
        
        travel(curr.left, sol, level + 1);
        travel(curr.right, sol, level + 1);
    }
}

İkili Ağac Ziqzaq Səviyyə Sifarişi üçün Python Kodu

class Solution:
    def zigzagLevelOrder(self, root):
        if not root: return []
        queue = deque([root])
        result, direction = [], 1
        
        while queue:
            level = []
            for i in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:  queue.append(node.left)
                if node.right: queue.append(node.right)
            result.append(level[::direction])
            direction *= (-1)
        return result

Binary Tree Ziqzaq Səviyyə Sifarişi üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi

O (N)

Kosmik Mürəkkəblik

O (N)

Crack Sistemi Dizayn Müsahibələri
Translate »