小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

104   leetcode - Maximum Depth of Binary Tree 

 雪柳花明 2016-09-25

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
題目很簡單，但考的很基礎(chǔ)。二叉樹的遍歷方式有兩種：遞歸和非遞歸，本題也有兩種解法。


本題為查詢樹的深度，我們采用直接遍歷二叉樹，并記錄我們訪問深度的方法即可。

可以考慮用一個全局變量記錄我們的深度，也可以通過DFS函數(shù)每一次返回當(dāng)前子樹的深度。

若采用返回值，則有

當(dāng)前樹長度 = max(左子樹深度, 右子樹深度) + 1



計算二叉樹的深度，簡單的前序遍歷即可。
遞歸算法：

點(diǎn)擊(此處)折疊或打開

  1. /**
  2.  * Definition for binary tree
  3.  * public class TreeNode {
  4.  * int val;
  5.  * TreeNode left;
  6.  * TreeNode right;
  7.  * TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     public int maxDepth(TreeNode root) {
  12.         int depth = 0;
  13.         if(root != null){
  14.             int leftDepth = maxDepth(root.left);
  15.             int rightDepth = maxDepth(root.right);
  16.             depth ++;
  17.             if(leftDepth < rightDepth){
  18.                 depth = depth + rightDepth;
  19.             }else{
  20.                 depth = depth + leftDepth;
  21.             }
  22.         }
  23.         return depth;
  24.     }
  25. }
非遞歸算法：
受后續(xù)遍歷二叉樹思想的啟發(fā)，想到可以利用后續(xù)遍歷的方法來求二叉樹的深度，在每一次輸出的地方替換成算棧S的大小，遍歷結(jié)束后最大的棧S長度即是棧的深度。
算法的執(zhí)行步驟如下：
（1）當(dāng)樹非空時，將指針p指向根節(jié)點(diǎn)，p為當(dāng)前節(jié)點(diǎn)指針。
（2）將p壓入棧S中，0壓入棧tag中，并令p執(zhí)行其左孩子。
（3）重復(fù)步驟（2），直到p為空。
（4）如果tag棧中的棧頂元素為1，跳至步驟（6）。從右子樹返回
（5）如果tag棧中的棧頂元素為0，跳至步驟（7）。從左子樹返回
（6）比較treedeep與棧的深度，取較大的賦給treedeep，對棧S和棧tag出棧操作，p指向NULL，并跳至步驟（8）。
（7）將p指向棧S棧頂元素的右孩子，彈出棧tag，并把1壓入棧tag。（另外一種方法，直接修改棧tag棧頂?shù)闹禐?也可以）
（8）循環(huán)（2）~（7），直到棧為空并且p為空
（9）返回treedeep，結(jié)束遍歷

點(diǎn)擊(此處)折疊或打開

  1. int TreeDeep(BinTree BT ){
  2.     int treedeep=0;
  3.     stack S;
  4.     stack tag;
  5.     BinTree p=BT;
  6.     while(p!=NULL||!isEmpty(S)){
  7.         while(p!=NULL){
  8.             push(S,p);
  9.             push(tag,0);
  10.             p=p->lchild;
  11.         }
  12.         if(Top(tag)==1){
  13.             deeptree=deeptree>S.length?deeptree:S.length;
  14.             pop(S);
  15.             pop(tag);
  16.             p=NULL;
  17.         }else{
  18.             p=Top(S);
  19.             p=p->rchild;
  20.             pop(tag);
  21.             push(tag,1);
  22.         }
  23.     }
  24.     return deeptree;
  25. }
前序、中序、和后序遍歷的遞歸和非遞歸實現(xiàn)，參考博文：
http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多