【未完成】【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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
