LeetCode104—Maximum Depth of Binary Tree

系统管理员 2022-08-21 04:58 26阅读 0赞

# LeetCode104—Maximum Depth of Binary Tree #

求二叉树的深度。

## 原题 ##

> 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.

## 两种解法 ##

### 深度优先搜索 ###

每次递归深度加1

#### **代码一** ####

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

网上大神写了一种更简洁的代码

#### **代码二** ####

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

### 层序遍历 ###

BFS对二叉树进行层序遍历，记录遍历的层数即可

#### **代码** ####

class Solution{
    public:
        int maxDepth(TreeNode* root){
            if (root == NULL)
                return 0;
            vector<TreeNode*>q;
            int front = 0;
            int rear = 1;
            int level = 0;
            q.push_back(root);
            while (front < q.size())
            {
                rear = q.size();
                while (front < rear)
                {
                    if (q[front]->left != NULL)
                    {
                        q.push_back(q[front]->left);
                    }
                    if (q[front]->right != NULL)
                    {
                        q.push_back(q[front]->right);
                    }
                    ++front;
                }
                ++level;
            }
            return level;
        }
    };