Binary Tree LeetCode Həllinin Tamlığını Yoxlayın

Problem bəyanat

Tamlığı yoxlayın a İkili ağac LeetCode Həlli - Nəzərə alınmaqla root ikili ağacın olub olmadığını müəyyən edin tam ikili ağac.

Tam ikili ağacda, bəlkə də sonuncu istisna olmaqla, hər səviyyə tamamilə doldurulur və sonuncu səviyyədəki bütün qovşaqlar mümkün qədər uzaqda qalır. Arasında ola bilər 1 və 2^h son səviyyədə daxil olmaqla qovşaqlar h.

Pin

misal

Test işi 1:

Input:

kök = [1, 2, 3, 4, 5, 6]

Çıxış:

doğru

Test işi 2:

Input:

kök = [1, 2, 3, 4, 5, null, 7]

Çıxış:

saxta

Izahat

i) Sonuncudan əvvəlki hər səviyyə doludur (yəni, qovşaq qiymətləri {1} və {2, 3} olan səviyyələr) və sonuncu səviyyədəki bütün qovşaqlar ({4, 5, 6}) mümkün qədər soldadır.

ii) 7 dəyəri olan qovşaq mümkün qədər solda deyil.

Yanaşma

Qeyd: Tam ikili ağacdır soldan doldurulmuş ola bilsin ki, ən aşağısı istisna olmaqla, bütün səviyyələrin tamamilə doldurulduğu ikili ağac. Tam ikili ağac tam ikili ağac kimidir, lakin iki əsas fərqi var. Bütün yarpaq elementləri sola əyilməlidir.

Tam ikili ağac üçün yalnız sonuncu səviyyədə boş bir node ola bilər. Boş node görünsə, sonradan heç bir etibarlı qovşaq görünməməlidir. Buna görə də, biz null dəyərini növbəyə qoya bilərik və hər dəfə null dəyəri gördükdə, seeEmptyNode bayrağını doğru olaraq təyin edirik. Əgər daha sonra etibarlı bir node görürüksə, ikili ağac tam ağac deyil.

Kodu

Binar ağacın tamlığını yoxlamaq üçün 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 boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        boolean seenNull = false;
        
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i<size; i ++){// Traverse all nodes on this level
                TreeNode curr = queue.poll();
                if(curr == null) {
                    seenNull = true;// When found null, set the flag
                }
                else {
                    if(seenNull) return false;// If found non null node, but flag is set. Return false
                    queue.offer(curr.left);
                    queue.offer(curr.right); 
                }
            }
        }
        return true;
    }
}

İkili ağacın tamlığını yoxlamaq üçün 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:
    bool isCompleteTree(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> q;
        q.push(root);
        bool foundNull = false;
        while(!q.empty())
        {
            TreeNode *curr = q.front();
            q.pop();
            if(curr->left)
            {
                if(foundNull)
                    return false;
                q.push(curr->left);
            }
            else
                foundNull = true;
            if(curr->right)
            {
                if(foundNull)
                    return false;
                q.push(curr->right);
            }
            else
                foundNull = true;
        }
        return true;
    }
};

İkili Ağacın Tamlığını Yoxlamaq üçün Mürəkkəblik Təhlili LeetCode Həll

Zamanın mürəkkəbliyi olacaq $O(n),$$burada\; n\; ağacdakı\; qovşaq\; sayıdır.$

Kosmik Mürəkkəblik olacaq $O(t),$$burada\; n\; ağacdakı\; qovşaq\; sayıdır.$

Referans: https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees