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.
方法一：
层次遍历，整棵树的层数，即二叉树的最大深度。主体的代码还是在层次遍历的基础上改成的。
/** * Definition for binary tree * 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 level=0; queue<TreeNode *> Q; Q.push(root); while( !Q.empty()) { int levNum=0; int count=Q.size(); //不能和下面的while条件写成levNUm<Q.size() //因为这样写以后，不遍历完整棵树，不会跳出 while(levNum<count) { TreeNode *temp=Q.front(); Q.pop(); if(temp->left) Q.push(temp->left); if(temp->right) Q.push(temp->right); levNum++; } level++; } return level; } };
方法二：
写法不一样，思想一样。
class Solution { public: int maxDepth(TreeNode* root) { if(!root) return 0; queue<TreeNode*> Q; int nCount=1; //某一层节点的个数 int nDepth=0; //层数 //基于BFS，引入两个计数器 Q.push(root); while(!Q.empty()) { TreeNode* pCur=Q.front(); Q.pop(); nCount--; if(pCur->left) Q.push(pCur->left); if(pCur->right) Q.push(pCur->right); if(!nCount) //保证遍历某一层时，深度不增加 { nDepth++; nCount=Q.size(); } } return nDepth; } }
方法三：
递归算法，终止条件为：节点不存在时，返回0，递归式为1+max(maxDepth(root->left),maxDepth(too->right))，即左右子树中的最大深度加上root所在层。
class Solution { public: int maxDepth(TreeNode* root) { if (root==NULL) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); } };
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
