题目描述:
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
思路:先想想递归该怎么做。如果一个节点是NULL,那么它的最大深度应该是0;如果它是一个孤立的节点,那么它的深度是1;否则它的深度应该是它所有孩子节点的最大深度+1。关系清晰明了,代码也很简单,如下:
public:
int maxDepth(TreeNode* root) {
if(root==NULL) return 0;
if((root->left || root->right)==NULL) return 1;
else return max(maxDepth(root->left),maxDepth(root->right))+1;
}
注意到其实第二个if语句作为递归出口,并不是必要的:因为对于孤立节点来说,它的孩子节点都是NULL,两个子树深度都是0,可以+1得到它自身的深度。好玩心起改写成1行代码:
int maxDepth(TreeNode* root) {
return root?max(maxDepth(root->left),maxDepth(root->right))+1:0;
}
上面两个算法时间复杂度都是O(n),测试运行时间都是 4ms。
下面试试能不能改成迭代算法:
最大深度,其实就是树的层数。所以模仿层序遍历就好了。不过这里要注意,要把层与层之间分开,然后统计遍历的层数。
int maxDepth(TreeNode* root) {
if(root==NULL) return 0;
//不能用栈,用队列
queue<TreeNode*> q;
int ans=0;
//用NULL作为层与层之间的分隔标志
q.push(root);
q.push(NULL);
while(true)
{
//每多一层,ans+1
ans++;
root=q.front();
q.pop();
while(root)
{
//既然NULL作为分隔标志了,这里的NULL就不能进入队列了
if(root->left) q.push(root->left);
if(root->right) q.push(root->right);
root=q.front();
q.pop();
}
if(q.size()==0) return ans;
q.push(NULL);
}
}
时间复杂度仍旧是O(n),测试运行时间 8ms。
;