LeetCode第104题 Maximum Depth of Binary Tree(c++)

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

 Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:

Input: root = [1,null,2]
Output: 2
Example 3:

Input: root = []
Output: 0
Example 4:

Input: root = [0]
Output: 1
 

Constraints:

The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目大意：

给定一个二叉树的头结点，求它的最大深度。

实现思路：

利用两个队列，进行bfs。

实现代码：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue q1;
        queue q2;
        if(root==NULL) return 0;
        int max=0;
        int num=1;
        q1.push(root);
        q2.push(num);
        while(!q1.empty()){
            TreeNode* temp=q1.front();
            int tmp=q2.front();
            q1.pop();
            q2.pop();
            if(temp->left){
                q1.push(temp->left);
                q2.push(tmp+1);
            }
            if(temp->right){
                q1.push(temp->right);
                q2.push(tmp+1);
            }
            if(tmp>max) max=tmp;
        }
        return max;
    }
};

 不过我的这种bfs因为建立了两个队列，空间复杂度较高，可以进行优化。

可以一层一层的拓展，减少一个队列的使用。

代码如下：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue q;
        if(root==NULL) return 0;
        int ans=0;
        q.push(root);
        while(!q.empty()){
            int n=q.size();
            while(n>0){
                TreeNode* tmp=q.front();
                q.pop();
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
                n--;
            }
            ans++;
        }
        return ans;
    }
};

这种方法是逐层遍历，也差不多。

第二种方法是dfs，通过递归来实现：

代码如下：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL) return 0;
        return max(maxDepth(root->left)+1,maxDepth(root->right)+1);
    }
};

这几种方法时间复杂度差不多，但是相对而言dfs的空间复杂度较低。