本节内容

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

104.二叉树的最大深度（优先掌握递归）※

建议：什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。

大家要先看视频讲解，就知道以上我说的内容了，很多录友刷过这道题，但理解的还不够。

题目链接： https://leetcode.cn/problems/maximum-depth-of-binary-tree/
文章讲解： https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html

题目分析

递归调用

class Solution {

    private int res = 0;

    public int maxDepth(TreeNode root) {

        recursion(root, 0);

        return res;
    }

    private void recursion(TreeNode root, int leave) {
        if (root == null) return;

        leave++;
        if (res < leave) {
            res = leave;
        }

        recursion(root.left, leave);
        recursion(root.right, leave);

    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:40.4 MB,击败了72.15% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

广度优先搜索（层序遍历）：迭代遍历

class Solution {

    private int res = 0;

    public int maxDepth(TreeNode root) {

        if (root == null) return res;
        // 层序遍历：迭代
        Deque<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            queue.offer(null);
            res++;
            while (queue.peek() != null) {
                TreeNode poll = queue.poll();
                if (poll.left != null)
                    queue.offer(poll.left);
                if (poll.right != null)
                    queue.offer(poll.right);
            }
            queue.poll();
        }

        return res;
    }
}

结果

解答成功:
执行耗时:2 ms,击败了2.59% 的Java用户
内存消耗:41.6 MB,击败了5.05% 的Java用户

代码随想录

https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html

递归法

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。

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

而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

先用后序遍历（左右中）来计算树的高度。

确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。

代码如下：

1	`int getdepth(TreeNode* node)`

确定终止条件：如果为空节点的话，就返回0，表示高度为0。

代码如下：

1	`if (node == NULL) return 0;`

确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

代码如下：

int leftdepth = getdepth(node->left);       // 左
int rightdepth = getdepth(node->right);     // 右
int depth = 1 + max(leftdepth, rightdepth); // 中
return depth;

本题当然也可以使用前序，代码如下：(充分表现出求深度回溯的过程)

代码实现

class solution {
    /**
     * 递归法
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

class Solution {
  /**
   * 递归法(求深度法)
   */
    //定义最大深度
    int maxnum = 0;

    public int maxDepth(TreeNode root) {
        ans(root,0);
        return maxnum;
    }
    
    //递归求解最大深度
    void ans(TreeNode tr,int tmp){
        if(tr==null) return;
        tmp++;
        maxnum = maxnum<tmp?tmp:maxnum;
        ans(tr.left,tmp);
        ans(tr.right,tmp);
        tmp--;
    }
}

迭代法

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：

所以这道题的迭代法就是一道模板题，可以使用二叉树层序遍历的模板来解决的。

class solution {
    /**
     * 迭代法，使用层序遍历
     */
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
        }
        return depth;
    }
}

559. N 叉树的最大深度

官方题目链接： 559. N 叉树的最大深度

题目分析

递归遍历

class Solution {
    private int res = 0;
    public int maxDepth(Node root) {
        recursion(root, 0);

        return res;
    }

    private void recursion(Node root, int leave) {
        if (root == null) return;
        leave++;
        if (res < leave) {
            res = leave;
        }
        for (Node node : root.children) {
            recursion(node, leave);
        }
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:41.7 MB,击败了54.70% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

迭代遍历：层序遍历

class Solution {
    private int res = 0;
    public int maxDepth(Node root) {
        // 迭代遍历：层序遍历
        if (root == null) return res;
        Deque<Node> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            queue.offer(null);
            res++;
            while (queue.peek() != null) {
                Node poll = queue.poll();
                for (Node node : poll.children) {
                    queue.offer(node);
                }
            }
            queue.poll();
        }
        return res;
    }
}

结果

解答成功:
执行耗时:3 ms,击败了4.28% 的Java用户
内存消耗:42.1 MB,击败了5.39% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

代码随想录

https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html#%E8%BF%AD%E4%BB%A3%E6%B3%95

思路：

依然可以提供递归法和迭代法，来解决这个问题，思路是和二叉树思路一样的，

代码实现

递归法

class Solution {
    /*递归法，后序遍历求root节点的高度*/
    public int maxDepth(Node root) {
        if (root == null) return 0;

        int depth = 0;
        if (root.children != null){
            for (Node child : root.children){
                depth = Math.max(depth, maxDepth(child));
            }
        }

        return depth + 1; //中节点
    }  
}

迭代法

class solution {
    /**
     * 迭代法，使用层序遍历
     */
    public int maxDepth(Node root) {
        if (root == null)   return 0;
        int depth = 0;
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty())
        {
            depth ++;
            int len = que.size();
            while (len > 0)
            {
                Node node = que.poll();
                for (int i = 0; i < node.children.size(); i++)
                    if (node.children.get(i) != null) 
                        que.offer(node.children.get(i));
                len--;
            }
        }
        return depth;
    }
}

111.二叉树的最小深度（优先掌握递归）※

建议：先看视频讲解，和最大深度看似差不多，其实差距还挺大，有坑。

题目链接： https://leetcode.cn/problems/minimum-depth-of-binary-tree/
文章讲解： https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html

题目分析

迭代法：层序遍历

class Solution {
    public int minDepth(TreeNode root) {

        // 迭代法：层序遍历
        if (root == null) return 0;
        int leave = 0;
        Deque<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            queue.offer(null);
            leave++;
            while (queue.peek() != null) {
                TreeNode poll = queue.poll();
                if (poll.left != null)
                    queue.offer(poll.left);
                if (poll.right != null)
                    queue.offer(poll.right);
                if (poll.right == null && poll.left == null)
                    return leave;
            }
            queue.poll();
        }
        return leave;
    }
}

结果

解答成功:
执行耗时:3 ms,击败了67.62% 的Java用户
内存消耗:60.2 MB,击败了79.19% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

递归法

class Solution {
    private int result = Integer.MAX_VALUE;

    public int minDepth(TreeNode root) {
        // 递归法
        if (root == null) return 0;
        recursion(root, 0);
        return result;
    }

    private void recursion(TreeNode root, int leave) {
        if (root == null) return;
        leave++;
        if (root.left == null && root.right == null && result > leave) {
            result = leave;
            return;
        }
        recursion(root.left, leave);
        recursion(root.right, leave);
    }
}

结果

解答成功:
执行耗时:7 ms,击败了63.08% 的Java用户
内存消耗:60.3 MB,击败了64.24% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html

思路

本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。

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

那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离也同样是最小深度。
以下讲解中遍历顺序上依然采用后序遍历（因为要比较递归返回之后的结果，本文我也给出前序遍历的写法）。
本题还有一个误区，在处理节点的过程中，最大深度很容易理解，最小深度就不那么好理解，如图：

这就重新审题了，题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。

递归法

递归三部曲：

确定递归函数的参数和返回值
参数为要传入的二叉树根节点，返回的是int类型的深度。

代码如下：

1	`int getDepth(TreeNode* node)`

确定终止条件
终止条件也是遇到空节点返回0，表示当前节点的高度为0。

代码如下：

1	`if (node == NULL) return 0;`

确定单层递归的逻辑
这块和求最大深度可就不一样了，一些同学可能会写如下代码：

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

这个代码就犯了此图中的误区：

如果这么求的话，没有左孩子的分支会算为最短深度。

所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

代码如下：

int leftDepth = getDepth(node->left);           // 左
int rightDepth = getDepth(node->right);         // 右
                                                // 中
// 当一个左子树为空，右不为空，这时并不是最低点
if (node->left == NULL && node->right != NULL) { 
    return 1 + rightDepth;
}   
// 当一个右子树为空，左不为空，这时并不是最低点
if (node->left != NULL && node->right == NULL) { 
    return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;

遍历的顺序为后序（左右中），可以看出：求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

代码实现

class Solution {
    /**
     * 递归法，相比求MaxDepth要复杂点
     * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        // 左右结点都不为null
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

迭代法

使用层序遍历的方式来解决
需要注意的是，只有当左右孩子都为空的时候，才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点

代码实现

class Solution {
   /**
     * 迭代法，层序遍历
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                if (poll.left == null && poll.right == null) {
                    // 是叶子结点，直接返回depth，因为从上往下遍历，所以该值就是最小值
                    return depth;
                }
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
    }
}

222.完全二叉树的节点个数（优先掌握递归）※

建议：需要了解，普通二叉树怎么求，完全二叉树又怎么求

题目链接： https://leetcode.cn/problems/count-complete-tree-nodes/
文章讲解： https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html

题目分析

递归遍历

单纯的按照普通二叉树来计算的

class Solution {
    public int countNodes(TreeNode root) {

        // 递归遍历
        if (root == null) return 0;

        int leftSum = countNodes(root.left);
        int rightSum = countNodes(root.right);

        return leftSum + rightSum + 1;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:44.7 MB,击败了35.34% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

迭代遍历：层序遍历

单纯的按照普通二叉树来计算的

class Solution {
    public int countNodes(TreeNode root) {
        // 迭代遍历：层序遍历
        if (root == null) return 0;

        Deque<TreeNode> queue = new LinkedList<>();
        int result = 0;

        queue.offer(root);

        while (!queue.isEmpty()) {
            queue.offer(null);
            while (queue.peek() != null) {
                TreeNode poll = queue.poll();
                result++;

                if (poll.left != null)
                    queue.offer(poll.left);
                if (poll.right != null)
                    queue.offer(poll.right);
            }
            queue.poll();
        }
        return result;
    }
}

结果

解答成功:
执行耗时:6 ms,击败了9.10% 的Java用户
内存消耗:43.9 MB,击败了92.21% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

代码随想录

https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html

普通二叉树

首先按照普通二叉树的逻辑来求。

这道题目的递归法和求二叉树的深度写法类似，而迭代法，层序遍历模板稍稍修改一下，记录遍历的节点数量就可以了。

递归遍历的顺序依然是后序（左右中）

递归

确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。

代码如下：

1	`int getNodesNum(TreeNode* cur) {`

确定终止条件：如果为空节点的话，就返回0，表示节点数为0。

代码如下：

1	`if (cur == NULL) return 0;`

确定单层递归的逻辑：先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一（加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。

代码如下：

int leftNum = getNodesNum(cur->left);      // 左
int rightNum = getNodesNum(cur->right);    // 右
int treeNum = leftNum + rightNum + 1;      // 中
return treeNum;

时间复杂度：O(n)
空间复杂度：O(log n)，算上了递归系统栈占用的空间

代码实现

class Solution {
    // 通用递归解法
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

迭代法

只要模板做少量改动，加一个变量result，统计节点数量就可以了

时间复杂度：O(n)
空间复杂度：O(n)

代码实现

class Solution {
    // 迭代法
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int result = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size -- > 0) {
                TreeNode cur = queue.poll();
                result++;
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return result;
    }
}

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

完全二叉树（一）如图：

完全二叉树（二）如图：

可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。

这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。如图：

在完全二叉树中，如果递归向左遍历的深度不等于递归向右遍历的深度，则说明不是满二叉树，如图：

那么，这种情况，递归向左遍历的深度等于递归向右遍历的深度，但也不是满二叉树，如题：

如果这么想，大家就是对完全二叉树理解有误区了，以上这棵二叉树，它根本就不是一个完全二叉树！

判断其子树是不是满二叉树，如果是则利用公式计算这个子树（满二叉树）的节点数量，如果不是则继续递归，那么在递归三部曲中，第二部：终止条件的写法应该是这样的：

if (root == nullptr) return 0; 
// 开始根据左深度和右深度是否相同来判断该子树是不是满二叉树
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
while (left) {  // 求左子树深度
    left = left->left;
    leftDepth++;
}
while (right) { // 求右子树深度
    right = right->right;
    rightDepth++;
}
if (leftDepth == rightDepth) {
    return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，返回满足满二叉树的子树节点数量
}

递归三部曲，第三部，单层递归的逻辑：（可以看出使用后序遍历）

int leftTreeNum = countNodes(root->left);       // 左
int rightTreeNum = countNodes(root->right);     // 右
int result = leftTreeNum + rightTreeNum + 1;    // 中
return result;

该部分精简之后代码为：

1	`return countNodes(root->left) + countNodes(root->right) + 1;`

最后整体C++代码如下：

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftDepth++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

时间复杂度：O(log n × log n)
空间复杂度：O(log n)

代码实现

class Solution {
    /**
     * 针对完全二叉树的解法
     *
     * 满二叉树的结点数为：2^depth - 1
     */
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left != null) {  // 求左子树深度
            left = left.left;
            leftDepth++;
        }
        while (right != null) { // 求右子树深度
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

02_1_代码随想录算法训练营18期

#LeetCode #算法训练营

14、第六章二叉树part03

http://yuanql.top/2023/07/27/02_1_代码随想录算法训练营18期/14、第六章二叉树part03/

作者

Qingli Yuan

发布于

2023年7月27日

许可协议

2023年7月27日每日一题--2500. 删除每行中的最大值上一篇

2023年7月26日每日一题--2569. 更新数组后处理求和查询下一篇

14、第六章 二叉树part03

本节内容

104.二叉树的最大深度 （优先掌握递归）※

题目分析

递归调用

结果

分析

广度优先搜索（层序遍历）：迭代遍历

结果

代码随想录

递归法

代码实现

迭代法

559. N 叉树的最大深度

题目分析

递归遍历

结果

分析

迭代遍历：层序遍历

结果

分析

代码随想录

代码实现

111.二叉树的最小深度 （优先掌握递归）※

题目分析

迭代法：层序遍历

结果

分析

递归法

结果

分析

代码随想录

思路

递归法

代码实现

迭代法

代码实现

222.完全二叉树的节点个数（优先掌握递归）※

题目分析

递归遍历

结果

分析

迭代遍历：层序遍历

结果

分析

代码随想录

普通二叉树

递归

代码实现

迭代法

代码实现

完全二叉树

代码实现

14、第六章二叉树part03

104.二叉树的最大深度（优先掌握递归）※

111.二叉树的最小深度（优先掌握递归）※