מאַקסימום דעפּט פון ביינערי בוים לעעטקאָדע לייזונג


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַדאָובי אַמאַזאָן facebook מייקראָסאָפֿט
ביינערי טרי רעקורסיאָן בוים טראַווערסאַל

פּראָבלעם סטאַטעמענט

אין דעם פּראָבלעם אַ ביינערי בוים איז געגעבן און מיר האָבן צו געפֿינען די מאַקסימום טיף פון דער געגעבן בוים. די מאַקסימום טיף פון אַ ביינערי בוים איז די נומער פון נאָודז אויף די לאָנגעסט דרך פֿון די וואָרצל נאָדע אַראָפּ צו די פאַרדאַסט בלאַט נאָדע.

בייַשפּיל

 
  3
 / \
9   20
   /  \		 
  15   7
3

דערקלערונג: עס זענען צוויי מעגלעך לאָנגעסט וועג ווי געוויזן אין רויט בוים.
מאַקסימום דעפּט פון ביינערי בוים לעעטקאָדע לייזונג

Empty Tree
0

ווי דער בוים איז ליידיק, די טיפקייַט איז 0.

0
1

ווי עס זענען בלויז איין נאָדע, די טיפקייַט איז 1.

צוגאַנג

צו געפֿינען די מאַקסימום טיפעניש פון דעם בוים, מיר קענען צולייגן אַ פּשוט רעקורסיווע צוגאַנג. וואו יעדער פונקציע רופן וועט פאָרשטעלן אַ סאַבסטרי וואָס האט וואָרצל נאָדע גערופֿן ווי 'וואָרצל'. מיר אַריבער די בוים דורך אַ רעקורסיווע פונקציע סטאַרטינג פֿון דער וואָרצל נאָדע.

אַזוי דער באַזע איז ווען די סובטרעע איז ליידיק, אָדער די שורש איז נאַל. אַזוי מיר אומקערן די טיפקייַט ווי 0.

אויב וואָרצל איז נישט נול, רופן די זעלבע פונקציע רעקורסיוועלי פֿאַר זיין לינקס קינד און רעכט קינד.

ווי געוויזן אין פיגורע, ווען די צוויי קינדער פונקציאָנירן די טיפעניש צוריק, מיר קלייַבן די מאַקסימום פון די צוויי סובטרעעס און צוריקקומען דעם ווערט נאָך אַדינג 1 צו אים (אַדדינג קראַנט נאָדע וואָס איז די פאָטער פון די צוויי סובטרעעס).

מאַקסימום דעפּט פון ביינערי בוים

ימפּלעמענטאַטיאָן

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

Java פּראָגראַם פֿאַר מאַקסימום טיף פון ביינערי בוים לעעטקאָדע סאַלושאַן

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר מאַקסימום דעפּט פון ביינערי בוים לעעטקאָדע לייזונג

צייט קאַמפּלעקסיטי

אָ (N):  מיר באַזוכן יעדער נאָדע פּונקט אַמאָל, אַזוי די צייט קאַמפּלעקסיטי איז O (N), ווו N איז די גאַנץ נומער פון נאָודז אין די געגעבן בוים.

ספעיס קאַמפּלעקסיטי 

אָ (N):  אין די ערגסט פאַל, דער בוים איז גאָר אַנבאַלאַנסט, למשל יעדער נאָדע האט בלויז לינקס קינד נאָדע אָדער נאָר רעכט קינד נאָדע, דאַן רעקורסיאָן רופן וואָלט פּאַסירן N מאָל (די הייך פון דעם בוים). דעריבער די מאַקסימום גרייס פון רופן אָנלייגן איז אָ (ען).
אין דער בעסטער פאַל (דער בוים איז גאָר באַלאַנסט), די הייך פון דעם בוים וואָלט זיין ⁡ (N). דעריבער, די פּלאַץ קאַמפּלעקסיטי אין דעם פאַל וואָלט זיין אָ (לאָג ⁡ (ן).