حداکثر عمق محلول کد باینری درخت  


سطح دشواری ساده
اغلب در خشت آمازون فیس بوک مایکروسافت
الگوریتم درخت باینری برنامه نویسی مصاحبه مصاحبه آماده LeetCode LeetCodeSolutions باز گشت عبور از درخت

بیان مسأله  

در مسئله a درخت دودویی داده شده است و ما باید حداکثر عمق درخت داده شده را پیدا کنیم. حداکثر عمق یک درخت باینری تعداد گره ها در طول طولانی ترین مسیر از گره ریشه به پایین ترین گره برگ است.

مثال

 
  3
 / \
9   20
   /  \		 
  15   7
3

توضیح: دو مسیر طولانی وجود دارد که در زیر درخت با رنگ قرمز نشان داده شده است.
حداکثر عمق محلول کد باینری درخت

Empty Tree

با خالی بودن درخت ، عمق آن 0 است.


1

از آنجا که فقط یک گره وجود دارد ، عمق 1 است.

روش  

برای یافتن حداکثر عمق درخت می توان از یک روش بازگشتی ساده استفاده کرد. که در آن هر فراخوانی عملکردی یک درخت فرعی را نشان می دهد که دارای گره ریشه است و به عنوان "root" نامیده می شود. ما درخت را با یک عملکرد بازگشتی از گره ریشه عبور می دهیم.

بنابراین حالت پایه زمانی است که درخت فرعی خالی باشد یعنی ریشه NULL باشد. بنابراین عمق را به صورت 0 برمی گردانیم.

اگر root NULL نیست ، همان عملکرد را به صورت بازگشتی برای فرزند چپ و راست کودک فراخوانی کنید.

همانطور که در شکل نشان داده شده است ، هنگامی که عملکرد دو کودک عمق خود را برمی گرداند ما حداکثر را از این دو درخت فرعی انتخاب می کنیم و پس از افزودن 1 به آن ، این مقدار را برمی گردانیم (افزودن گره فعلی که والد دو درخت فرعی است).

همچنین مشاهده کنید
K شکافهای خالی LeetCode

حداکثر عمق درخت دودوییسنجاق

پیاده سازی  

برنامه C ++ برای حداکثر عمق محلول کد باینری درخت

#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

برنامه جاوا برای حداکثر عمق راه حل کد کد باینری

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

تجزیه و تحلیل پیچیدگی برای حداکثر عمق محلول کد دودویی درخت باینری  

پیچیدگی زمان

بر) :  ما دقیقاً یکبار از هر گره بازدید می کنیم ، بنابراین پیچیدگی زمان O (N) است ، جایی که N تعداد کل گره های درخت داده شده است.

پیچیدگی فضا 

بر) :  در بدترین حالت ، درخت کاملاً نامتعادل است ، به عنوان مثال هر گره فقط گره کودک را ترک کرده است یا فقط گره کودک راست را دارد ، سپس تماس برگشتی N بار اتفاق می افتد (ارتفاع درخت). بنابراین حداکثر اندازه پشته تماس O (N) خواهد بود.
در بهترین حالت (درخت کاملاً متعادل است) ، ارتفاع درخت log⁡ (N) خواهد بود. بنابراین ، پیچیدگی فضا در این حالت O (log⁡ (N) خواهد بود.