ความลึกขั้นต่ำของโซลูชัน Leetcode แบบไบนารีทรี


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน แอปเปิล Facebook
ต้นไม้ไบนารี การค้นหาครั้งแรกที่กว้าง การค้นหาครั้งแรกเชิงลึก

ในปัญหานี้เราต้องหาความยาวของเส้นทางที่สั้นที่สุดจากรากไปยังใบไม้ใด ๆ ในช่วงเวลาที่กำหนด ต้นไม้ไบนารี. โปรดสังเกตว่า“ ความยาวของเส้นทาง” ในที่นี้หมายถึงจำนวนโหนดจากโหนดรูทไปยังโหนดลีฟ ความยาวนี้เรียกว่าความลึกขั้นต่ำของต้นไม้ไบนารี

ตัวอย่าง

อินพุต

ความลึกขั้นต่ำของโซลูชัน Leetcode แบบไบนารีทรี

 

 

 

 

 

 

 

2

คำอธิบาย

เส้นทางที่สั้นที่สุดคือ: 2 -> 1 ซึ่งมีความยาว 2

อินพุต

 

 

 

 

 

 

 

3

คำอธิบาย

เส้นทางที่สั้นที่สุดคือ: 1 -> 2 -> 3ความยาว 3

แนวทาง (เรียกซ้ำ)

ปัญหานี้มีโครงสร้างเหมือนกับการหาความสูงของต้นไม้ไบนารี แต่ในกรณีนี้เราต้องหาความสูง / ความลึกขั้นต่ำระหว่างรากกับใบไม้ใด ๆ ในต้นไม้ เราสามารถดึงความลึกต่ำสุดของต้นไม้ย่อยซ้ายและขวาของรูทได้โดยใช้ การค้นหาครั้งแรกเชิงลึก (DFS) แล้วส่งกลับค่าต่ำสุดของความลึกทั้งสอง เราจำเป็นต้องพิจารณาบางกรณีเมื่อต้นไม้ย่อยด้านซ้ายและด้านขวาของโหนดอยู่ NULL. หากทรีย่อยด้านซ้ายคือ โมฆะ มันจะกลับมามีความสูงเท่ากับ แต่เนื่องจากเราไม่พบใบไม้ในทรีย่อยนี้ดังนั้นสิ่งนี้ จะเป็นคำตอบที่ผิด ดังนั้นเราจำเป็นต้องเรียกใช้ฟังก์ชันวนซ้ำเมื่อโหนดถูกเรียกใช้เท่านั้น ไม่ โมฆะ

ขั้นตอนวิธี

  1. สร้างฟังก์ชัน minDepth () เพื่อส่งกลับความลึกต่ำสุดของรูทที่ผ่าน
  2. ถ้ารากเป็น NULL, กลับ 0
  3. ในกรณีที่ทั้ง ซ้าย และ ขวา subtrees คือ NULLกลับ 1
  4. หากทรีย่อยด้านซ้ายคือ NULL, กลับ 1 + minDepth (รูท -> ขวา)
  5. มิฉะนั้นในกรณีที่แผนผังย่อยที่ถูกต้องคือ NULL, กลับ 1 + minDepth (รูท -> ซ้าย)
  6. ผลตอบแทน 1 + ขั้นต่ำ (นาทีความลึก(ราก -> ซ้าย), นาทีความลึก(รูท -> ขวา))

การปรับใช้ความลึกขั้นต่ำของโซลูชัน Leetcode แบบไบนารีทรี

โปรแกรม C ++

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

int minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    if(root->left == NULL && root->right == NULL)
        return 1;
    if(root->left == NULL)
        return 1 + minDepth(root->right);
    if(root->right == NULL)
        return 1 + minDepth(root->left);
    return 1 + min(minDepth(root->left) , minDepth(root->right));
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}

โปรแกรม Java

import java.util.*;

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

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        if(root.left == null)
            return 1 + minDepth(root.right);
        if(root.right == null)
            return 1 + minDepth(root.left);
        return 1 + Math.min(minDepth(root.left) , minDepth(root.right));

    }
}
2

การวิเคราะห์ความซับซ้อนของความลึกขั้นต่ำของโซลูชัน Leetcode แบบไบนารีทรี

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

บน)ในขณะที่เราสำรวจต้นไม้ทั้งต้นแม้ในกรณีที่เลวร้ายที่สุด

ความซับซ้อนของพื้นที่

บน). เมื่อต้นไม้ไบนารีเอียงเฟรมสแต็กแบบเรียกซ้ำอาจใช้พื้นที่ไม่เกิน O (N)

แนวทาง (ย้ำ)

เราสามารถใช้ การค้นหาแบบกว้าง - แรก (BFS) เพื่อค้นหาโหนดแรกซึ่งเป็นใบไม้และส่งกลับความลึกจากราก เราสามารถใช้คิวเพื่อเก็บคู่ของโหนดและความลึกจากโหนดรูท เมื่อเราได้รับโหนดซึ่งเป็นใบไม้เราจะส่งกลับความลึก

ขั้นตอนวิธี

  1. ถ้ารูทคือ NULL, กลับ 0
  2. เริ่มต้นคิวของคู่ของโหนดต้นไม้และจำนวนเต็ม
  3. ดันโหนดรูทไปที่คิวโดยมีความลึกเป็น 1
  4. ในขณะที่คิวไม่ว่าง:
    • ดึงความลึกและแอดเดรสโหนดขององค์ประกอบคิวด้านหน้า
    • นำรายการออกจากคิว
    • ถ้าโหนดหน้าคือ NULLคืนความลึก
    • กดปุ่ม ซ้าย และ ขวา โหนดไปยังต้นไม้หากเป็นเช่นนั้น ไม่ โมฆะ
  5. กล้บ -1 เพื่อรักษาไวยากรณ์ของโปรแกรมเนื่องจากฟังก์ชันจะส่งกลับจำนวนเต็ม

การปรับใช้ความลึกขั้นต่ำของโซลูชัน Leetcode แบบไบนารีทรี

โปรแกรม C ++

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

int minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    queue < pair <treeNode* , int> > q;
    q.push({root , 1});

    treeNode* frontNode;
    int depth;

    while(!q.empty())
    {
        frontNode = q.front().first;
        depth = q.front().second;
        q.pop();

        if(frontNode->left == NULL && frontNode->right == NULL)
            return depth;

        if(frontNode->left != NULL)
            q.push({frontNode->left , depth + 1});

        if(frontNode->right != NULL)
            q.push({frontNode->right , depth + 1});
    }
    return -1;
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}


โปรแกรม Java

import java.util.*;

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

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> q = new LinkedList<>();
        q.add(new Pair(root , 1));

        treeNode frontNode;
        int depth;

        while(q.size() > 0)
        {
            frontNode = q.peek().key;
            depth = q.peek().value;

            q.remove();

            if(frontNode.left == null && frontNode.right == null)
                return depth;

            if(frontNode.left != null)
                q.add(new Pair(frontNode.left , depth + 1));

            if(frontNode.right != null)
                q.add(new Pair(frontNode.right , depth + 1));
        }
        return -1;
    }
}
2

การวิเคราะห์ความซับซ้อนของความลึกขั้นต่ำของโซลูชัน Leetcode แบบไบนารีทรี

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

บน)ในขณะที่เราสำรวจต้นไม้ทั้งต้นอีกครั้ง

ความซับซ้อนของพื้นที่

บน)เนื่องจากเราใช้คิวเพื่อเก็บรายละเอียดของทุกโหนด