Day 16 | Leetcode 104, 559, 111, 222

链接

104.二叉树的最大深度
 111.二叉树的最小深度
 222.完全二叉树的节点个数

知识

104.二叉树的最大深度

111.二叉树的最小深度

222.完全二叉树的节点个数

初次尝试

104.二叉树的最大深度

我看到本题后，发现本题在层序遍历里面做过，就用层序遍历先求解。写出了如下代码：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);
        int res = 0;
        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res ++ ;
        }
        return res;
    }
};

本题应该可以尝试用别的遍历方法，比如递归去求解。直接看卡尔的视频讲解吧。

559. n叉树的最大深度

本题我首先尝试用层序遍历的解法求解，写出了如下的可以AC的代码：

class Solution {
public:
    int maxDepth(Node* root) {
        queue<Node*> q;
        int height = 0;

        if (root != NULL) q.push(root);

        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                Node* node = q.front();
                q.pop();

                for (int i = 0; i < node->children.size(); i ++ )
                    if (node->children[i]) q.push(node->children[i]);
            }
            height ++ ;
        }
        return height;
    }
};

接着思考如何递归求解。递归知道思路，但写不出取孩子树最大高度的那部分关键代码。

111.二叉树的最小深度

本题可以用层序遍历来做，属于层序遍历的10道题之一。我写出了如下的代码：

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> q;
        int depth = 0;

        if (root != NULL) q.push(root);

        while (q.size())
        {
            int size = q.size();
            depth ++ ;
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
                if (!node->left && !node->right) return depth;
            }
        }
        return depth;
    }
};

我再尝试用递归求解。发现有坑，做不出来，看卡尔的讲解。

222.完全二叉树的节点个数

拿到本题，我的第一想法依然是层序遍历。不得不说层序遍历法可以解决很多问题。我写下了如下的代码：

class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);

        int cnt = 0;

        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                cnt ++ ;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return cnt;
    }
};

感叹下，层序遍历确实能解决很多题，应该还不止卡尔给出的那10道题。我再来尝试递归解法。我觉得应该采用后序遍历，先统计根节点左右子树的节点数量，将二者加起来再加1即可。我写出了如下的代码：

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL) return 0;

        // 后序遍历：左右中
        int left = countNodes(root->left);
        int right = countNodes(root->right);
        int cnt = left + right + 1;
        return cnt;
    }
};

这道题我能想到的解法就是这两种，接着看卡尔的讲解。

实现

104.二叉树的最大深度

什么是深度，什么是高度？

深度：二叉树中任意一个节点到根节点的距离。根节点的深度规定为1（0也可以，规则不同）。
高度：二叉树中任意一个节点到叶子节点的距离。叶子节点的高度规定为1。

求高度用后序遍历，求深度用前序遍历。求高度是从下往上计数，因此要求从下往上遍历，而后序遍历顺序为左右中，恰好就是从下往上。求深度是从上往下计数，因此要求从上往下遍历，而前序遍历顺序为中左右。恰好就是从上往下。本题本来应该用前序遍历，但根节点的高度就是二叉树的最大深度，因此本题用后序遍历也可以做。

递归三部曲：

传入的参数和返回值
1
int getheight(TreeNode* node)

终止条件

if (node == NULL) return 0; // 叶子节点的高度是1，其下的空节点高度是0

单层递归（后序遍历：左右中）

int leftheight = getheight(node->left); // 左节点高度
int rightheight = getheight(node->right); // 右节点高度
int height = 1 + max(leftheight, rightheight); // 中节点高度，为左右孩子的高度取最大值+1
return height; // 根节点的高度就是二叉树的最大深度

本题的前序遍历写法相比于后序遍历写法要复杂很多（前序遍历还涉及到回溯的过程）。本题也可以用迭代法实现。

559. n叉树的最大深度

受到代码随想录的启发，写出了递归法（类似后序遍历）的代码：

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == NULL) return 0; // 终止条件
        
        // 挑选出最高的孩子节点，将其高度记为height
        int height = 0;
        for (int i = 0; i < root->children.size(); i ++ )
            height = max(height, maxDepth(root->children[i]));
        height ++ ; // 中节点（父节点）的高度在最高的孩子节点的基础上+1
        
        return height;
    }
};

111.二叉树的最小深度

本题和二叉树的最大深度有很多细节不同，容易踩坑。最小深度：根节点到叶子节点的最小距离（根节点到最近的叶子节点的距离）。像104题一样，本题求二叉树的最小深度，也可以通过后序遍历求高度的方式来求解。二叉树的最小深度实际上就是根节点的最小高度。本题求深度，本来应该用前序遍历，但前序遍历的代码不如后序遍历简洁，因此本题依然推荐使用后序遍历。

误区，不能写：int height = 1 + min(left, right);，若根节点的左子树为空，右子树不为空，则这样写二叉树的最小深度为1，显然不对。正确的方法是取右子树的最小高度，然后+1。为处理这种情况，需要写如下的单次递归的代码：

int left = getheight(node->left);
int right = getheight(node->right);
// 若根节点的左子树为空，右子树不为空，二叉树的最小深度为右子树的最小高度+1
if (node->left == NULL && node->right != NULL)
    return 1 + right;
// 若根节点的左子树不为空，右子树为空，二叉树的最小深度为左子树的最小高度+1
if (node->left != NULL && node->right == NULL)
    return 1 + left;
// 若左右子树都不为空，则取其中最小的最小高度+1返回
int res = 1 + min(left, right);
return res;

本题后序遍历的完整写法如下所示：

// 后序遍历
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;

        int left = minDepth(root->left);
        int right = minDepth(root->right);

        // 左子树为空，右子树非空
        // 也可写作if (left == 0 && right) 
        if (root->left == NULL && root->right != NULL) 
            return 1 + right;
        // 左子树非空，右子树为空
        // 也可写作if (left && right == 0)
        if (root->left != NULL && root->right == NULL)
            return 1 + left;
        // 左右子树都不为空
        int res = 1 + min(left, right);
        return res;
    }
};

我写出了一个精简后的版本，但并不会影响代码的可读性（依然可以轻松看出后序遍历）：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;

        int left = minDepth(root->left); // 左
        int right = minDepth(root->right); // 右
        
        // 中
        if (!left && right) return 1 + right; // 左空右不空
        if (left && !right) return 1 + left; // 左不空右空
        return 1 + min(left, right); // 左右都不空
    }
};

222.完全二叉树的节点个数

普通二叉树，递归法（前中后序）和迭代法（层序遍历）都可以求二叉树的节点个数。我在初次尝试中写的两个版本的代码都是把本题中的二叉树当成了普通二叉树，而没有利用完全二叉树的特性。本题强调了完全二叉树，就是暗示我们尽量利用完全二叉树的特性。

在递归法（前中后序）中，后序遍历的代码是最简洁的。每个节点都遍历了一遍，时间复杂度是O(n)。接下来利用完全二叉树的特性来降低时间复杂度。完全二叉树：除了底层节点，上面的节点都是满的。底层节点从左到右依次排开。对于满二叉树，只要知道深度h，节点数目就是2^h - 1。对于完全二叉树，如果其子树是满二叉树，则可以直接用上述公式来计算，计算完左右子树的节点数再+1（根节点）即可。关键：如何判断子树为满二叉树，并求其深度。

对于满二叉树，一直向左遍历和一直向右遍历的深度应该是相等的。一直向左遍历和一直向右遍历的深度相等的完全二叉树的子树一定是满二叉树。若遇到子树非满二叉树的情况，则继续向下遍历（即继续遍历子树的左右子树），直到是满二叉树为止，然后不断返回并+1。这种方式利用了完全二叉树的特性，且避免了遍历没有必要的节点，时间复杂度小于O(n)。

int getNum(TreeNode* node)
{
    // 终止条件1
    if (node == NULL) return 0; 
    
    // 终止条件2：遇到子树为满二叉树的情况，则返回子树中节点的数量
    TreeNode* left = node->left; // 用于遍历子树的左侧
    TreeNode* right = node->right; // 用于遍历子树的右侧
    int leftdepth = 0, rightdepth = 0; // 左侧和右侧的深度
    // 计算左侧的深度
    while (left)
    {
        left = left->left;
        leftdepth ++ ;
    }
    // 计算右侧的深度
    while (right)
    {
        right = right->right;
        rightdepth ++ ;
    }
    // 左右侧深度相等，说明子树是满二叉树，可以利用公式快速计算子树的节点数量
    if (leftdepth == rightdepth) return (2 << leftdepth) - 1; // 2 << 0 = 2^1, 2 << 1 = 2^2
    
    // 单层递归的逻辑，后序遍历
    leftnum = getNum(node->left); // 左子树数量
    rightnum = getNum(node->right); // 右子树数量
    int res = leftnum + rightnum + 1; // 中
    return res;
}

上述解法不需要去遍历完全二叉树中的所有节点，而是用公式直接计算子树为满二叉树时的节点数量并返回。

心得与备忘录

104.二叉树的最大深度

本题可以用层序遍历法求解，属于层序遍历法可以求解的10道题之一。但本题用递归（后序遍历）求解代码最为简洁。
注意二叉树中深度和高度这两个概念。某个节点的深度指其到根节点的距离，某个节点的高度指其到叶子节点的距离。这两个概念可以说是相反的。
求深度用前序遍历，求高度用后序遍历。
二叉树的最大深度就是根节点的高度。因此本题可以用后序遍历求解，实际上后序遍历的代码远比前序遍历的代码简单。因此本题的推荐做法就是后序遍历。
对于559. n叉树的最大深度。同样可以采用类似后序遍历的递归方法和层序遍历的迭代方法。对于递归方法，注意如何挑选出最高的孩子节点。

111.二叉树的最小深度

本题可以用迭代法（层序遍历）和递归法（前/后序遍历）求解。最推荐的方法是后序遍历，因为其代码最为简洁。
后序遍历是用来求高度的，但二叉树的最小深度就是根节点的最小高度，因此本题可以用后序遍历。
本题的易错点为：不可以直接将104题的max改成min（因为二叉树的最小深度为根节点到叶子节点的最小距离），而是要针对左右子树是否为空进行分类讨论。
本题的层序遍历写法同样需要注意：只有当左右孩子都为空的时候，才说明遍历到最低点了。

222.完全二叉树的节点个数

本题可以采用递归写法和迭代写法。递归写法建议采用后序遍历，迭代写法建议采用层序遍历。二者的时间复杂度都是O(n)。
上述方法对普通二叉树都适用，但对本题的完全二叉树，充分利用其特性可将时间复杂度进一步减小。
一直向左遍历和一直向右遍历的深度相等的完全二叉树的子树一定是满二叉树。若遇到子树非满二叉树的情况，则继续向下遍历，最终必然会遇到满二叉树。对于满二叉树，只要知道深度h，节点数目就是2^h - 1。因此不需要遍历完全二叉树的每一个节点，就可以求得其节点的个数。
上述解法的终止条件有两个，一个是遇到叶子节点，另一个是子树为满二叉树。单层递归逻辑采用后序遍历写法。
时间复杂度分析：递归调用的次数=树的高度=log n，每层递归需要计算子树的高度，故也是log n。因此总的时间复杂度为O(log n * log n)。
空间复杂度分析：递归的深度（即递归调用栈的最大深度）大约是树的高度。对于一棵平衡二叉树来说，其高度大约是log n，其中n是树中节点的数量。故空间复杂度为O(log n)。