ความลึกสูงสุดของโซลูชัน Leetcode แบบไบนารีทรี  


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

คำชี้แจงปัญหา  

ในปัญหาก ต้นไม้ไบนารี ได้รับและเราต้องหาความลึกสูงสุดของต้นไม้ที่กำหนด ความลึกสูงสุดของต้นไม้ไบนารีคือจำนวนโหนดตามเส้นทางที่ยาวที่สุดจากโหนดรูทลงไปยังโหนดลีฟที่ไกลที่สุด

ตัวอย่าง

 
  3
 / \
9   20
   /  \		 
  15   7
3

คำอธิบาย: มีสองเส้นทางที่ยาวที่สุดที่เป็นไปได้ดังที่แสดงในต้นไม้ด้านล่างเป็นสีแดง
ความลึกสูงสุดของโซลูชัน Leetcode แบบไบนารีทรี

Empty Tree

เนื่องจากต้นไม้ว่างเปล่าความลึกคือ 0


1

เนื่องจากมีเพียงโหนดเดียวความลึกคือ 1

เข้าใกล้  

ในการค้นหาความลึกสูงสุดของต้นไม้เราสามารถใช้วิธีการวนซ้ำง่ายๆ โดยที่การเรียกใช้ฟังก์ชันแต่ละครั้งจะแสดงถึงทรีย่อยซึ่งมีโหนดรูทเรียกว่า 'รูท' เราสำรวจต้นไม้ด้วยฟังก์ชันวนซ้ำโดยเริ่มจากโหนดรูท

ดังนั้นกรณีพื้นฐานคือเมื่อทรีย่อยว่างเช่นรูทเป็นโมฆะ เราจึงคืนค่าความลึกเป็น 0

ถ้า root ไม่ใช่ NULL ให้เรียกใช้ฟังก์ชันเดียวกันซ้ำสำหรับชายด์ซ้ายและชายด์ขวา

ดังที่แสดงในรูปเมื่อฟังก์ชันชายด์สองฟังก์ชันส่งกลับความลึกเราจะเลือกค่าสูงสุดจากต้นไม้ย่อยทั้งสองนี้และส่งคืนค่านี้หลังจากเพิ่ม 1 เข้าไป (การเพิ่มโหนดปัจจุบันซึ่งเป็นพาเรนต์ของต้นไม้ย่อยทั้งสอง)

ดูสิ่งนี้ด้วย
K ช่องว่าง LeetCode

ความลึกสูงสุดของไบนารีทรีหมุด

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

โปรแกรม C ++ สำหรับความลึกสูงสุดของโซลูชัน Leetcode แบบไบนารีทรี

#include <bits/stdc++.h>
using namespace std;
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) {}
};

int maxDepth(TreeNode* root) 
{
    if(root==NULL) return 0;
    return 1+max(maxDepth(root->left),maxDepth(root->right));
}

int main() 
{
    TreeNode *root= new TreeNode(3);
    root->left= new TreeNode(9);
    root->right= new TreeNode(20);
    root->right->left= new TreeNode(15);
    root->right->right= new TreeNode(7);
    
    cout<<maxDepth(root)<<endl; 
  return 0; 
}
3

โปรแกรม Java สำหรับความลึกสูงสุดของโซลูชัน Leetcode แบบไบนารีทรี

import java.util.*;
import java.lang.*;
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 MaxDepth
{  
    public static int maxDepth(TreeNode root) 
    {
        if(root==null) return 0;
        
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
    
    public static void main(String args[])
    {
        TreeNode root= new TreeNode(3);
        root.left= new TreeNode(9);
        root.right= new TreeNode(20);
        root.right.left= new TreeNode(15);
        root.right.right= new TreeNode(7);
       
        System.out.println(maxDepth(root));
        
    }
}
3

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

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

บน) :  เราเยี่ยมชมแต่ละโหนดเพียงครั้งเดียวดังนั้นความซับซ้อนของเวลาคือ O (N) โดยที่ N คือจำนวนโหนดทั้งหมดในทรีที่กำหนด

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

บน) :  ในกรณีที่เลวร้ายที่สุดต้นไม้จะไม่สมดุลอย่างสมบูรณ์เช่นแต่ละโหนดมีเพียงโหนดลูกทางซ้ายหรือโหนดลูกด้านขวาเท่านั้นจากนั้นการเรียกซ้ำจะเกิดขึ้น N ครั้ง (ความสูงของต้นไม้) ดังนั้นขนาดสูงสุดของ call stack คือ O (N)
ในกรณีที่ดีที่สุด (ต้นไม้มีความสมดุลอย่างสมบูรณ์) ความสูงของต้นไม้จะเป็นlog⁡ (N) ดังนั้นความซับซ้อนของพื้นที่ในกรณีนี้จะเป็น O (log⁡ (N)