104 二叉树的最大深度 easy

跟定二叉树，返回其最大深度。

简单的思路就是使用迭代法，做一个层序遍历，记录深度就行。代码如下：

int maxDepth(TreeNode* root) {
    
      
    if (!root) return 0;
    int depth = 0;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
    
      
        int size = que.size();
        for (int i = 0; i < size; i++) {
    
      
            TreeNode *node = que.front();
            que.pop();

            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
        depth++;
    }
    return depth;
}

另一种思路就是使用递归，本题使用前序遍历或者后序遍历都可以，根据随想录中的说法，使用前序求得是深度，而使用后序求的是高度。

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
• 二叉树节点的高度：指从该节点（本题中就是从根节点开始）到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

为什么前序遍历可以求深度，而后序遍历可以求高度呢？我们简单说一下，因为前序遍历的顺序是中左右，先遍历中间结点，再往下层处理，直到遍历到某个叶子结点；而后序遍历的顺序则是左右中，先遍历下层结点，或者可以说先遍历到叶子结点，最后回到中间结点。所以前序是一直往下挖，求深度；而后序则是先从某个底层出发，往上钻。

使用递归法，因为我们要获取深度，所以返回类型是整型，而传入参数则必然是结点；

当遍历到空结点的时候就回调，前序遍历的处理逻辑就是，从当前结点的左右孩子出发，调用递归函数，返回其中最大值 + 1（加一因为当前结点也属于一层）。

代码如下：

int reverse(TreeNode *cur) {
    
      
    if (!cur) return 0;
    int leftDepth = reverse(cur->left);
    int rightDepth = reverse(cur->right);
    int depth = 1 + max(leftDepth, rightDepth);

    return depth;
}
int maxDepth(TreeNode* root) {
    
      
    if (!root) return 0;
    return reverse(root);
}

559 N叉树的最大深度 easy

如果使用迭代法，那么和此前N叉树的层序遍历是一样的，每一层的遍历需要使用循环。

代码如下：

int maxDepth(Node* root) {
    
      
    queue<Node*> que;
    if (root != NULL) que.push(root);
    int depth = 0;
    while (!que.empty()) {
    
      
        int size = que.size();
        depth++; // 记录深度
        for (int i = 0; i < size; i++) {
    
      
            Node* node = que.front();
            que.pop();
            for (int j = 0; j < node->children.size(); j++) {
    
      
                if (node->children[j]) que.push(node->children[j]);
            }
        }
    }
    return depth;
}

使用递归法也是一样的，代码如下：

int reverse(Node *cur) {
    
      
    if (!cur) return 0;
    int maxDepth = 0;
    for (int i = 0; i < cur->children.size(); i++) {
    
      
        int depth = reverse(cur->children[i]);
        if (depth > maxDepth) 
            maxDepth = depth;
    }
    return maxDepth + 1;
}
int maxDepth(Node* root) {
    
      
    if (!root) return 0;
    return reverse(root);
}

111 二叉树的最小深度 easy

此处要强调一下最小深度的定义：从根节点到最近叶子结点的最短路径上结点数量。

这里若使用递归法，函数返回类型和传入参数，以及结束条件都是一样的，不同之处就在于处理逻辑：

如果和刚刚一样处理，写成以下这样，其实是不对的。如果一个结点没有左子树，返回值就会是1，并不一定能找到最小深度（回归定义）。

int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);
return result;

所以，此处的处理逻辑要复杂一些，如果有一个子树为空，就不是最小深度，整体代码如下：

int minDepth(TreeNode* root) {
    
      
    if (root == NULL) return 0;
    if (root->left == NULL && root->right != NULL) {
    
      
        return 1 + minDepth(root->right);
    }
    if (root->left != NULL && root->right == NULL) {
    
      
        return 1 + minDepth(root->left);
    }
    return 1 + min(minDepth(root->left), minDepth(root->right));
}

迭代法也是相似的处理逻辑，代码如下：

int minDepth(TreeNode* root) {
    
      
    if (root == NULL) return 0;
    int depth = 0;
    queue<TreeNode*> que;
    que.push(root);
    while(!que.empty()) {
    
      
        int size = que.size();
        depth++; // 记录最小深度
        for (int i = 0; i < size; i++) {
    
      
            TreeNode* node = que.front();
            que.pop();
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
            // 此处就是不同之处
            if (!node->left && !node->right) {
    
       
                return depth;
            }
        }
    }
    return depth;
}