104-二叉树的最大深度

LeetCode

发布日期: 2021-07-11

LeetCode 104. Maximum Depth of Binary Tree

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

method 1: 递归

递归参数：节点
递归结束条件：节点为空，返回0
单层递归逻辑：当前节点的左子树高度和右子树高度的较大值+1，就是该节点子树的高度

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

method 2: 层序遍历

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;  // 记录有多少层
    while (!q.empty()) {
        int size = q.size();
        depth++;
        for (int i = 0; i < size; ++i) {
            TreeNode* top = q.front();
            q.pop();
            if (top->left) q.push(top->left);
            if (top->right) q.push(top->right);
        }
    }
    return depth;
}

LeetCode 559. Maximum Depth of N-ary Tree

LeetCode-559

Given a n-ary 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.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

method: 递归

注意：二叉树只有两个结果所以直接

return max(leftDepth, rightDepth);

这里有N个结果，显然不能一个一个列出来，所以换一种写法，记录每一次的结果

for (int i = 0; i < N; ++i) {
    depth = max(depth, childrenDepth);
}
return depth;

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

LeetCode 111. Minimum Depth of Binary Tree

LeetCode-111

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1:

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

method 1: 递归

如果子树为空的话不能算深度为0，因为只有叶子节点才算深度

左子树为空，右子树非空，返回右子树高度+1

右子树为空，左子树非空，返回左子树高度+1

左右子树都非空，返回较小者+1；叶子结点也算在这种情况里

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

或者这样写

int res = INT_MAX;
void dfs(TreeNode *root, int depth) {
    if (!root) return;
    if (!root->left && !root->right) {
        res = min(res, depth);  // 叶子节点才能更新
    }
    dfs(root->left, depth + 1);
    dfs(root->right, depth + 1);
}
int minDepth(TreeNode* root) {
    if (!root) return 0;
    dfs(root, 1);
    return res;
}

method 2: 层序遍历

错误写法

int minDepth(TreeNode* root) {
    queue<TreeNode*> q;
    if (root == nullptr) return 0;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        int size = q.size();
        depth++;
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = q.front();
            q.pop();
            if (cur->left) q.push(cur->left);
            else if (cur->right) q.push(cur->right);    // 不能用else
            else break;     // 不能用break
        }
    }
    return depth;
}

else 是分支语句，执行了if就不会执行 else，这样右节点就不会被放进来
break 退出当前 for 循环，但外面还有一个 while 循环，破坏了层序遍历的结构

正确写法

三种情况分别用三个if判断
没有左子树和右子树，说明是叶子节点，可以返回了

int minDepth(TreeNode* root) {
    queue<TreeNode*> q;
    if (root == nullptr) return 0;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        int size = q.size();
        depth++;
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = q.front();
            q.pop();
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
            if (!cur->left && !cur->right) return depth;
        }
    }
    return depth;
}