الفنون رقم 017

ARTS هو نشاط بدأه 由左耳朵耗子--陈皓: قم بإجراء سؤال واحد على الأقل عن خوارزمية leetcode كل أسبوع، واقرأ مقالًا تقنيًا واحدًا على الأقل باللغة الإنجليزية وعلق عليه، وتعلم مهارة فنية واحدة على الأقل، وشارك المقالة مع الآراء والأفكار. (أي أن الخوارزمية والمراجعة والنصائح والمشاركة يشار إليها باسم ARTS) وتستمر لمدة عام واحد على الأقل.

الفنون 017

هذه المادة 17

سؤال خوارزمية الخوارزمية

222. عدد عقد الشجرة الكاملة

صعوبة السؤال: متوسطة

بالنظر إلى شجرة ثنائية كاملة، قم بحساب عدد العقد.

ملاحظة:

<u style=“display: inline;”>تعريف شجرة ثنائية كاملة من :</u> في الشجرة الثنائية الكاملة، يتم ملء كل مستوى، باستثناء المستوى الأخير، بالكامل، وتكون جميع العقد في المستوى الأخير في أقصى اليسار قدر الإمكان. يمكن أن تحتوي على ما بين 1 و2^h عقدة شاملة في المستوى الأخير h.

مثال:

**Input:** 
    1
   / \
  2   3
 / \  /
4  5 6

**Output:** 6```



#### الحل

اللغة: **ج**

```c
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

الطريقة الأولى، العودية:

int countNodes(struct TreeNode* root) {
        if (!root) {
        return 0;
    }

    int count = 1;
    if (root->left) {
        count +=countNodes(root->left);
    }
    if (root->right) {
        count +=countNodes(root->right);
    }
}

انتهت مهلة الخوارزمية المذكورة أعلاه. رأيت حلول الآخرين على النحو التالي:

الطريقة الثانية:

int countNodes(struct TreeNode* root) {
    if(!root) return 0;
    if(root->val!=INT_MAX){
        root->val=INT_MAX;
        return 1+countNodes(root->left)+countNodes(root->right);
    }
    return -1111111;
}

في الواقع، الخوارزميتان المذكورتان أعلاه كلاهما متكررة، لكن الخوارزمية تنتهي مرة واحدة، لكن الخوارزمية الثانية عادية، ووقت التشغيل هو 12 مللي ثانية فقط. لا أفهم سبب كون الشرط if (root->val!=INT_MAX) مفيدًا. هذا الشرط صحيح بالتأكيد. لماذا يمكن اجتياز حالة اختبار LeetCode إذا تمت إضافة هذا الشرط، ولكن ستنتهي المهلة إذا لم تتم إضافته؟ ؟

الطريقة الثالثة: استخدام التكرار

int countNodes(struct TreeNode* root) {
    if (!root) {
        return 0;
    }
  struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
    int count = 0;
    int index = 0;
    struct TreeNode* p= root;
    
    while (p) {
        ++count;
        printf("%d,%d=;;;;",count,p->val);
        if (p->right) {
            printf("ooooooo");
            stack[index++] = p->right;
        }
        
        p = p->left;
        
        if (!p && index > 0) {
            printf("kkkkkkkkkkk");
            p =  stack[--index];
        }
    }
    
    return count;
}

وهذا أيضا سوف تنتهي مهلة. في الواقع، الطريقتان الأولى والثالثة عبارة عن اجتياز شجرة ثنائية، لكنهما سينتهيان هنا جميعًا.

الطريقة الرابعة:

int countNodes(struct TreeNode* root)
{
    /* get left depth and right depth */
    struct TreeNode *pL = root, *pR = root;
    int dep = 0;
    for(; pL && pR; dep++)
    {
        pL = pL->left;
        pR = pR->right;
    }
    
    /* count the full tree collectively */
    if(!pL && !pR) return (1<<dep) -1;
    
    /* count left and right sub-trees separately */
    return countNodes(root->left) + 1 + countNodes(root->right);
}

على الرغم من أن هذه الخوارزمية تستخدم أيضًا التكرار، إلا أنها تستخدم خصائص الشجرة الثنائية الكاملة. من السهل جدًا حساب عدد العقد لشجرة ثنائية كاملة.

الطريقة الخامسة

int height(struct TreeNode *root)
{
    int h;
    
    h = -1;
    while (root) {
        ++h;
        root = root->left;
    }
    return h;
}

int countNodes(struct TreeNode* root)
{
    int h1, h2;
    
    
    if (!root) return 0;
    
    h1 = height(root->left);
    h2 = height(root->right);
    
    if (h1 == h2) {
        //说明左子树是满树 (1 << (h1 + 1)) - 1) 是左子树节点的个数
        return 1 + ((1 << (h1 + 1)) - 1) + countNodes(root->right);
    } else {
         //说明右子树是满树 ，((1 << h1) - 1) 是右子树节点的个数
        return 1 + ((1 << h1) - 1) + countNodes(root->left);
    }
}

تستفيد هذه الخوارزمية أيضًا من خصائص الشجرة الثنائية الكاملة. إذا فهمت الكود الموجود في جزء التعليق، فسوف تفهم الخوارزمية بأكملها.

مراجعة

أنظر أيضا: https://dandan2009.github.io/2018/11/27/data-structures-part2-a-quick-comparison/

نصائح

فهم ثابت مرة أخرى.

يتم الإعلان عن المتغيرات التالية في أسلوب في فئة:

static int x;

افترض أن اسم الفئة هو A، ثم قم بإنشاء كائنات A: a1, a2. في هذا الوقت المتغير

على الرغم من أن هذه نقطة معرفة قديمة جدًا، إلا أنه من الممكن أن تقوم بحسابات خاطئة عن طريق الخطأ عند استخدام ثابت، ومن الصعب استكشاف الأخطاء وإصلاحها، لذلك يجب أن تفكر جيدًا قبل استخدام ثابت.

شارك

Google Cloud مجاني لمدة عام واحد: https://cloud.google.com/free/ عند التسجيل، يجب أن يكون لديك بطاقة ائتمان بالعملة الأجنبية، مثل بطاقة التأشيرة. من أجل منع التسجيل الضار، ستقوم Google بخصم دولار واحد من بطاقة الائتمان عند التسجيل، ولكنها ستعيده بعد فترة.

شارك https://github.com/tracyone/v2ray.fun v2ray بنقرة واحدة

https://233yes.com/post/1/ تركيب مقاوم للخداع