【未完成】【LeetCode】104. Maximum Depth of Binary Tree
- 2019 年 11 月 7 日
- 筆記
版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。
本文鏈接：https://blog.csdn.net/shiliang97/article/details/102795178
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.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3 / 9 20 / 15 7 return its depth = 3.
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree 著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
完成了，就是只用了遞歸，另外兩種解題思路
廣度隊列和深度的堆棧還沒看呢。。。。。
遞歸、棧循環實現深度優先遍歷；用隊列循環實現層遍歷。借鑒了伊利亞·穆羅梅茨的程式碼。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ //深度優先：遞歸版 class Solution { public: int maxDepth(TreeNode* root) { if(root==NULL) return 0; int l=maxDepth(root->left)+1; int r=maxDepth(root->right)+1; return l>r?l:r; } }; //深度優先：用棧的循環版 class Solution { public: int maxDepth(TreeNode* root) { if(root==NULL) return 0; stack<pair<TreeNode*,int>> s; TreeNode* p=root; int Maxdeep=0; int deep=0; while(!s.empty()||p!=NULL)//若棧非空，則說明還有一些節點的右子樹尚未探索；若p非空，意味著還有一些節點的左子樹尚未探索 { while(p!=NULL)//優先往左邊走 { s.push(pair<TreeNode*,int>(p,++deep)); p=p->left; } p=s.top().first;//若左邊無路，就預備右拐。右拐之前，記錄右拐點的基本資訊 deep=s.top().second; if(Maxdeep<deep) Maxdeep=deep;//預備右拐時，比較當前節點深度和之前存儲的最大深度 s.pop();//將右拐點出棧；此時棧頂為右拐點的前一個結點。在右拐點的右子樹全被遍歷完後，會預備在這個節點右拐 p=p->right; } return Maxdeep; } }; //廣度優先：使用隊列 class Solution { public: int maxDepth(TreeNode* root) { if(root==NULL) return 0; deque<TreeNode*> q; q.push_back(root); int deep=0; while(!q.empty()) { deep++; int num=q.size(); for(int i=1;i<=num;i++) { TreeNode* p=q.front(); q.pop_front(); if(p->left) q.push_back(p->left); if(p->right) q.push_back(p->right); } } return deep; } };
作者：zzxh 鏈接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/cde-san-chong-fang-fa-shi-xian-you-zhu-jie-by-zzxh/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。
