根据前序计算完整二叉树的深度-yiteyi-C++库

给定二叉树的前序，计算其深度（或高度） [从深度0开始]。前序是一个包含两个可能字符的字符串。

null

“l”表示叶子
“n”表示内部节点

给定的树可以看作是一个完整的二叉树，其中每个节点都有0或两个子节点。节点的两个子节点可以是“n”或“l”，也可以是两者的混合。 例如：

Input  : nlnllOutput : 2Explanation :

图片[1]-根据前序计算完整二叉树的深度-yiteyi-C++库

Input  : nlnnlllOutput : 3

图片[2]-根据前序计算完整二叉树的深度-yiteyi-C++库

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

给出了二叉树的前序此外，我们将得到一个char字符串（由’n’和’l’组成），因此也不需要实现tree。递归函数是： 1）基本情况：返回0；当树[i]=“l”或i>=strlen（树） 2） find_depth（tree[i++]）//左子树 3） find_depth（tree[i++]）//右子树其中i是字符串树的索引。

C++

                         // C++ program to find height of full binary tree                       
                         // using preorder                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to return max of left subtree height                       
                         // or right subtree height                       
                         int                                     findDepthRec(                                     char                                     tree[],                                     int                                     n,                                     int                                     & index)                       
                         {                       
                                                 if                                     (index >= n || tree[index] ==                                     'l'                                     )                       
                                                 return                                     0;                       
           
                                                 // calc height of left subtree (In preorder                       
                                                 // left subtree is processed before right)                       
                                                 index++;                       
                                                 int                                     left = findDepthRec(tree, n, index);                       
           
                                                 // calc height of right subtree                       
                                                 index++;                       
                                                 int                                     right = findDepthRec(tree, n, index);                       
           
                                                 return                                     max(left, right) + 1;                       
                         }                       
           
                         // Wrapper over findDepthRec()                       
                         int                                     findDepth(                                     char                                     tree[],                                     int                                     n)                       
                         {                       
                                                 int                                     index = 0;                       
                                                 findDepthRec(tree, n, index);                       
                         }                       
           
                         // Driver program                       
                         int                                     main()                       
                         {                       
                                                 // Your C++ Code                       
                                                 char                                     tree[] =                                     "nlnnlll"                                     ;                       
                                                 int                                     n =                                     strlen                                     (tree);                       
           
                                                 cout << findDepth(tree, n) << endl;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find height                       
                         // of full binary tree using                       
                         // preorder                       
                         import                                     java .io.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 // function to return max                       
                                                 // of left subtree height                       
                                                 // or right subtree height                       
                                                 static                                     int                                     findDepthRec(String tree,                       
                                                 int                                     n,                                     int                                     index)                       
                                                 {                       
                                                 if                                     (index >= n ||                       
                                                 tree.charAt(index) ==                                     'l'                                     )                       
                                                 return                                     0                                     ;                       
           
                                                 // calc height of left subtree                       
                                                 // (In preorder left subtree                       
                                                 // is processed before right)                       
                                                 index++;                       
                                                 int                                     left = findDepthRec(tree,                       
                                                 n, index);                       
           
                                                 // calc height of                       
                                                 // right subtree                       
                                                 index++;                       
                                                 int                                     right = findDepthRec(tree, n, index);                       
           
                                                 return                                     Math.max(left, right) +                                     1                                     ;                       
                                                 }                       
           
                                                 // Wrapper over findDepthRec()                       
                                                 static                                     int                                     findDepth(String tree,                       
                                                 int                                     n)                       
                                                 {                       
                                                 int                                     index =                                     0                                     ;                       
                                                 return                                     (findDepthRec(tree,                       
                                                 n, index));                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 static                                     public                                     void                                     main(String[] args)                       
                                                 {                       
                                                 String tree =                                     "nlnnlll"                                     ;                       
                                                 int                                     n = tree.length();                       
                                                 System.out.println(findDepth(tree, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed                       
                         // by anuj_67.                       

Python3

                         #Python program to find height of full binary tree                       
                         # using preorder                       
                                   
                         # function to return max of left subtree height                       
                         # or right subtree height                       
                         def                                     findDepthRec(tree, n, index) :                       
           
                                                 if                                     (index[                                     0                                     ] >                                     =                                     n                                     or                                     tree[index[                                     0                                     ]]                                     =                                     =                                     'l'                                     ):                       
                                                 return                                     0                       
           
                                                 # calc height of left subtree (In preorder                       
                                                 # left subtree is processed before right)                       
                                                 index[                                     0                                     ]                                     +                                     =                                     1                       
                                                 left                                     =                                     findDepthRec(tree, n, index)                       
           
                                                 # calc height of right subtree                       
                                                 index[                                     0                                     ]                                     +                                     =                                     1                       
                                                 right                                     =                                     findDepthRec(tree, n, index)                       
                                                 return                                     (                                     max                                     (left, right)                                     +                                     1                                     )                       
           
                         # Wrapper over findDepthRec()                       
                         def                                     findDepth(tree, n) :                       
           
                                                 index                                     =                                     [                                     0                                     ]                       
                                                 return                                     findDepthRec(tree, n, index)                       
           
                                   
                         # Driver program to test above functions                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 tree                                     =                                     "nlnnlll"                       
                                                 n                                     =                                     len                                     (tree)                       
           
                                                 print                                     (findDepth(tree, n))                       
           
                         # This code is contributed by SHUBHAMSINGH10                       

C#

                         // C# program to find height of                       
                         // full binary tree using preorder                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // function to return max of left subtree                       
                                                 // height or right subtree height                       
                                                 static                                     int                                     findDepthRec(                                     char                                     [] tree,                                     int                                     n,                                     int                                     index)                       
                                                 {                       
                                                 if                                     (index >= n || tree[index] ==                                     'l'                                     )                       
                                                 return                                     0;                       
           
                                                 // calc height of left subtree (In preorder                       
                                                 // left subtree is processed before right)                       
                                                 index++;                       
                                                 int                                     left = findDepthRec(tree, n, index);                       
           
                                                 // calc height of right subtree                       
                                                 index++;                       
                                                 int                                     right = findDepthRec(tree, n, index);                       
           
                                                 return                                     Math.Max(left, right) + 1;                       
                                                 }                       
           
                                                 // Wrapper over findDepthRec()                       
                                                 static                                     int                                     findDepth(                                     char                                     [] tree,                                     int                                     n)                       
                                                 {                       
                                                 int                                     index = 0;                       
                                                 return                                     (findDepthRec(tree, n, index));                       
                                                 }                       
           
                                                 // Driver program                       
                                                 static                                     public                                     void                                     Main()                       
                                                 {                       
                                                 char                                     [] tree =                                     "nlnnlll"                                     .ToCharArray();                       
                                                 int                                     n = tree.Length;                       
                                                 Console.WriteLine(findDepth(tree, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

Javascript

                         <script>                       
                                                 // Javascript program to find height of                       
                                                 // full binary tree using preorder                       
                                   
                                                 // function to return max of left subtree                       
                                                 // height or right subtree height                       
                                                 function                                     findDepthRec(tree, n, index)                       
                                                 {                       
                                                 if                                     (index >= n || tree[index] ==                                     'l'                                     )                       
                                                 return                                     0;                       
                                   
                                                 // calc height of left subtree (In preorder                       
                                                 // left subtree is processed before right)                       
                                                 index++;                       
                                                 let left = findDepthRec(tree, n, index);                       
                                   
                                                 // calc height of right subtree                       
                                                 index++;                       
                                                 let right = findDepthRec(tree, n, index);                       
                                   
                                                 return                                     Math.max(left, right) + 1;                       
                                                 }                       
                                   
                                                 // Wrapper over findDepthRec()                       
                                                 function                                     findDepth(tree, n)                       
                                                 {                       
                                                 let index = 0;                       
                                                 return                                     (findDepthRec(tree, n, index));                       
                                                 }                       
                                   
                                                 let tree =                                     "nlnnlll"                                     .split(                                     ''                                     );                       
                                                 let n = tree.length;                       
                                                 document.write(findDepth(tree, n));                       
                                   
                         </script>                       

输出：

时间复杂性： O（N）

辅助空间： O（1）

本文由 舒巴姆·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章