ผลรวมด้านซ้ายออกจาก Leetcode Solutions  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี
อัลกอริทึม การเข้ารหัส สัมภาษณ์ สัมภาษณ์เตรียม LeetCode LeetCodeSolutions ต้นไม้ ทรีทราเวอร์ซัล

ในปัญหานี้เราต้องหาผลรวมของใบไม้ที่เหลือทั้งหมดเป็นเลขฐานสอง ต้นไม้. ใบไม้ที่เรียกว่าใบซ้าย"ถ้าเป็นชายด์ทางซ้ายของโหนดใด ๆ ในทรี

ผลรวมด้านซ้ายออกจาก Leetcode Solutionsหมุด

ตัวอย่าง    

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

เข้าใกล้  

เราสามารถใช้การเรียกซ้ำเพื่อสำรวจต้นไม้ไบนารี หากโหนดใดมีลูกทางซ้ายและเป็นใบไม้ด้วยเราสามารถเพิ่มมูลค่าของลูกทางซ้ายลงในผลรวมของเราได้ แต่วิธีนี้ใช้พื้นที่สแต็กแบบเรียกซ้ำ

เราสามารถใช้การส่งผ่านอื่น ๆ ที่สามารถประหยัดพื้นที่หน่วยความจำได้หรือไม่?

Morris Inorder Traversal สามารถนำไปใช้เพื่อเยี่ยมชมทุกโหนดซ้ำ ๆ ตรวจสอบว่ามีลูกใบซ้ายหรือไม่และเพิ่มมูลค่าตามลำดับในผลลัพธ์ นี่คือแนวทางที่ดีที่สุด โปรดทราบว่าเราสามารถใช้“ Morris Inorder traversal” ได้ก็ต่อเมื่อปัญหาอนุญาตให้เราเปลี่ยนโครงสร้างของต้นไม้ได้

อัลกอริทึม (เรียกซ้ำ)  

  1. สร้างฟังก์ชัน sumOfLeftLeaves () ที่ส่งคืนผลรวมของใบทางซ้ายของการส่งผ่านใด ๆ ราก
  2. ถ้ารากของต้นไม้นั้น NULL
    • กลับศูนย์
  3. หากรูทปัจจุบันมีลูกด้านซ้ายและเป็นไฟล์ ใบไม้
    • คืนค่า + sumOfLeftLEaves (root-> left) + sumOfLeftLeaves (root-> right)
  4. ส่งคืน sumOfLeftLEaves (รูท -> ซ้าย) + sumOfLeftLeaves (รูท -> ขวา)
ดูสิ่งนี้ด้วย
ค้นหาผู้ชนะใน Tic Tac Toe Game Leetcode Solution

อัลกอริทึม (Morris Inorder)  

  1. สำรวจไบนารีโดยใช้ Morris Inorder Traversal:
    • เธรดลำดับก่อนหน้าของแผนผังย่อยด้านซ้ายของโหนดใด ๆ เข้ากับตัวเอง
    • หากมีเธรดอยู่แล้วให้คลายเกลียวออกเพื่อคงโครงสร้างเดิมของต้นไม้ไว้
  2. ถ้าชายด์ด้านซ้ายของโหนดใด ๆ เป็นใบไม้ให้เพิ่มลงในผลลัพธ์
  3. พิมพ์ผลลัพธ์

การดำเนินงาน  

โปรแกรม C ++ ของ Sum of Left Leaves Leetcode Solutions

วิธีการวนซ้ำ

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int sumOfLeftLeaves(treeNode* root)
{
    if(root)
    {
        if(root->left && !root->left->left && !root->left->right)
            return root->left->value + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
    return 0;
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(4);
    root->right = new treeNode(7);
    root->right->left = new treeNode(9);
    root->right->right =  new treeNode(4);

    cout << "Sum is " << sumOfLeftLeaves(root) << "\n";


    return 0;
}

วิธีที่เหมาะสมที่สุด

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int sumOfLeftLeaves(treeNode* root)
{
    int sum = 0;
    while(root != NULL)
    {
        if(root->left == NULL)
        {
            if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
                sum += root->left->value;
            root = root->right;
        }
        else
        {
            treeNode* temp = root->left;
            while(temp->right != NULL && temp->right != root)
                temp = temp->right;

            if(temp->right == NULL)
            {
                temp->right = root;
                root = root->left;
            }
            else
            {
                temp->right = NULL;
                if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
                    sum += root->left->value;
                root = root->right;
            }
        }
    }
    return sum;
}



int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(4);
    root->right = new treeNode(7);
    root->right->left = new treeNode(9);
    root->right->right =  new treeNode(4);

    cout << "Sum is " << sumOfLeftLeaves(root) << "\n";


    return 0;
}
Sum is 13

โปรแกรม Java ของ Sum of Left Leaves Leetcode Solutions

วิธีการวนซ้ำ

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class sum_of_left_leaves
{
    public static int sumOfLeftLeaves(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left != null && root.left.left == null && root.left.right == null)
            return root.left.value + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(4);
        root.right = new treeNode(7);
        root.right.left = new treeNode(9);
        root.right.right =  new treeNode(4);

        System.out.println("Sum is " + sumOfLeftLeaves(root));
    }
}

วิธีที่เหมาะสมที่สุด

int sum = 0;
        while(root != null)
        {
            if(root.left == null)
            {
                if(root.left != null && root.left.left == null && root.left.right == null)
                    sum += root.left.value;
                root = root.right;
            }
            else
            {
                treeNode temp = root.left;
                while(temp.right != null && temp.right != root)
                    temp = temp.right;

                if(temp.right == null)
                {
                    temp.right = root;
                    root = root.left;
                }
                else
                {
                    temp.right = null;
                    if(root.left != null && root.left.left == null && root.left.right == null)
                        sum += root.left.value;
                    root = root.right;
                }
            }
        }
        return sum;
Sum is 13

การวิเคราะห์ความซับซ้อนของผลรวมของใบซ้าย Leetcode Solutions  

ความซับซ้อนของเวลา

บน), ในขณะที่เราสำรวจต้นไม้ทั้งต้นหนึ่งครั้งทั้งในแบบวนซ้ำและแบบวนซ้ำ

ดูสิ่งนี้ด้วย
เวลาที่ดีที่สุดในการซื้อและขายหุ้น

ความซับซ้อนของอวกาศ

O (1) โดยใช้ Morris Inorder Traversal วิธีการเรียกซ้ำจะใช้ บน) พื้นที่ในหน่วยความจำ.