devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

14.树(3) | 二叉树的最大深度、n叉树的最大深度、二叉树的最小深度、完全二叉树的节点个数_n叉树的高度

作者：我家小花儿 | 2024-07-26 23:22:41

赞

踩

n叉树的高度

        今天的题目都与二叉树的深度或高度相关，所以需要对相关概念熟悉：

  • 二叉树节点的深度：根节点->该节点。最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）；
  • 二叉树节点的高度：该节点->叶子节点。最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）；
  • 二叉树的最小深度：根节点到最近叶子节点（左右孩子都为空的节点才是叶子节点）的最短路径上的节点数量；
  • 根节点的高度就是二叉树的最大深度；
  • 前序求的是深度（因为每进入一层+1），后序求的是高度（因为每回退一层+1）。

        这次的题在有了前面的基础后大都不难。有些题目的递归只需要以当前节点为空作为出口，有些则需要以当前节点无子节点作为出口。前者的root为空情况会在递归函数内处理，后者的这一情况会在主函数中处理。另外关于二叉树深度、高度、完全二叉树、满二叉树的相关计算和判断方法需要熟悉。

        第1题（104.二叉树的最大深度）的递归解法的后序遍历方法比较简单，取左右子树深度的最大值，再得到当前树的深度最大值。

  1. class Solution {
  2. public:
  3.     int getDepth(TreeNode* cur, int depth) {
  4.         if (cur == nullptr) {
  5.             return depth;
  6.         }
  7.         int depthLeft = getDepth(cur->left, depth + 1);
  8.         int depthRight = getDepth(cur->right, depth + 1);
  9.         return max(depthLeft, depthRight);
  10.     }
  11.     int maxDepth(TreeNode* root) {
  12.         return getDepth(root, 0);
  13.     }
  14. };

        也可以用前序遍历，需要设定一个全局变量depth，首先用当前节点更新depth，再先后用左、右子树更新depth，返回最后的depth。

  1. class Solution {
  2. public:
  3.     int ans;
  4.     void getDepth(TreeNode* cur, int depth) {
  5.         if (cur == nullptr) {
  6.             ans = max(ans, depth);
  7.             return;
  8.         }
  9.         getDepth(cur->left, depth + 1);
  10.         getDepth(cur->right, depth + 1);
  11.     }
  12.     int maxDepth(TreeNode* root) {
  13.         ans = 0;
  14.         getDepth(root, 0);
  15.         return ans;
  16.     }
  17. };

而题解的写法更为清晰，将root为空的情况独立在主函数中处理，然后将当前节点无子节点的情况作为递归出口，并确保左、右子节点非空时才对其进行递归。

  1. class Solution {
  2. public:
  3.     int ans;
  4.     void getDepth(TreeNode* cur, int depth) {
  5.         if (cur->left == nullptr && cur->right == nullptr) {
  6.             ans = max(ans, depth);
  7.             return;
  8.         }
  9.         if (cur->left != nullptr) {
  10.             getDepth(cur->left, depth + 1);
  11.         }
  12.         if (cur->right != nullptr) {
  13.             getDepth(cur->right, depth + 1);
  14.         }
  15.     }
  16.     int maxDepth(TreeNode* root) {
  17.         if (root == nullptr) {
  18.             return 0;
  19.         }
  20.         ans = 0;
  21.         getDepth(root, 1);
  22.         return ans;
  23.     }
  24. };

       迭代解法即二叉树的层序遍历，在遍历途中记录总共有多少层即可。

  1. class Solution {
  2. public:
  3.     int maxDepth(TreeNode* root) {
  4.         if (root == nullptr) {
  5.             return 0;
  6.         }
  7.         queue<TreeNode*> que;
  8.         que.push(root);
  9.         int depth = 0;
  10.         while (!que.empty()) {
  11.             int size = que.size();
  12.             ++depth;
  13.             for (int i = 0; i < size; ++i) {
  14.                 TreeNode *cur = que.front();
  15.                 que.pop();
  16.                 if (cur->left) {
  17.                     que.push(cur->left);
  18.                 }
  19.                 if (cur->right) {
  20.                     que.push(cur->right);
  21.                 }
  22.             }
  23.         }
  24.         return depth;
  25.     }
  26. };

         二刷：更简单的写法：

  1. class Solution {
  2. public:
  3.     int maxDepth(TreeNode* root) {
  4.         if (root == nullptr) {
  5.             return 0;
  6.         }
  7.         return max(maxDepth(root->left), maxDepth(root->right)) + 1;
  8.     }
  9. };

        第2题（559.n叉树的最大深度）相比第1题（104.二叉树的最大深度）只是二叉树变为n叉树。后序遍历的递归解法也只需要改为在取depth时取所有子节点depth的最大值即可。要注意遍历所有子节点之前，depth初始化为depth + 1，而不是0。否则如果当前节点的子节点个数为0时就不会进行遍历，最终就会直接返回0。

  1. class Solution {
  2. public:
  3.     int getDepth(Node* cur, int depth) {
  4.         if (cur == nullptr) {
  5.             return depth;
  6.         }
  7.         int depthMax = depth + 1;
  8.         vector<Node*> children = cur->children;
  9.         for (int i = 0; i < children.size(); ++i) {
  10.             depthMax = max(depthMax, getDepth(children[i], depth + 1));
  11.         }
  12.         return depthMax;
  13.     }
  14.     int maxDepth(Node* root) {
  15.         return getDepth(root, 0);
  16.     }
  17. };

        前序遍历的递归解法则需要注意一点，用children的size()作为循环的次数的话，如果size()为0，即没有子节点，那么循环就不会进行，其中的递归也不会进行，不会像上一题 （104.二叉树的最大深度）的前序遍历递归解法一样将空指针传入函数作为递归参数，所以depth + 1也不会作为参数，res在此时不会更新。解决方法就是在第9行这里就将depth更新为depth + 1。

  1. class Solution {
  2. public:
  3.     int res;
  4.     void getDepth(Node* cur, int depth) {
  5.         res = max(res, depth);
  6.         if (cur == nullptr) {
  7.             return;
  8.         }
  9.         res = max(res, depth + 1);
  10.         vector<Node*> children = cur->children;
  11.         for (int i = 0; i < children.size(); ++i) {
  12.             getDepth(children[i], depth + 1);
  13.         }
  14.     }
  15.     int maxDepth(Node* root) {
  16.         res = 0;
  17.         getDepth(root, 0);
  18.         return res;
  19.     }
  20. };

        而如果使用与上一题题解的前序递归一致的写法，就不会有上面的问题，就仍与二叉树情况是一致的。

  1. class Solution {
  2. public:
  3.     int res;
  4.     void getDepth(Node* cur, int depth) {
  5.         vector<Node*> children = cur->children;
  6.         if (children.size() == 0) {
  7.             res = max(res, depth);
  8.             return;
  9.         }
  10.         for (int i = 0; i < children.size(); ++i) {
  11.             getDepth(children[i], depth + 1);
  12.         }
  13.     }
  14.     int maxDepth(Node* root) {
  15.         if (root == nullptr) {
  16.             return 0;
  17.         }
  18.         res = 0;
  19.         getDepth(root, 1);
  20.         return res;
  21.     }
  22. };

        迭代法与上一题（104.二叉树的最大深度）除了要放入队列的节点数增多外没有其他区别。

  1. class Solution {
  2. public:
  3.     int maxDepth(Node* root) {
  4.         if (root == nullptr) {
  5.             return 0;
  6.         }
  7.         queue<Node*> que;
  8.         que.push(root);
  9.         int depth = 0;
  10.         while (!que.empty()) {
  11.             int size = que.size();
  12.             ++depth;
  13.             for (int i = 0; i < size; ++i) {
  14.                 Node *cur = que.front();
  15.                 que.pop();
  16.                 vector<Node*> children = cur->children;
  17.                 for (int i = 0; i < children.size(); ++i) {
  18.                     que.push(children[i]);
  19.                 }
  20.             }
  21.         }
  22.         return depth;
  23.     }
  24. };

         二刷：更简单的写法：

  1. class Solution {
  2. public:
  3.     int maxDepth(Node* root) {
  4.         if (root == nullptr) {
  5.             return 0;
  6.         }
  7.         int ans = 1; // 不能设置为0，因为当前节点非空已经说明当前节点深度至少为1了
  8.         for (Node* child : root->children) {
  9.             ans = max(ans, maxDepth(child) + 1);
  10.         }
  11.         return ans;
  12.     }
  13. };

        第3题（111.二叉树的最小深度）所求的最小深度即为二叉树的最小高度，所以递归法采用后序遍历和前序遍历均可。需要注意的是如果左右节点的某一个为空，因为题目所说的最小深度是根节点->最近叶子节点上的节点数，那么当前节点的最小高度不是1，而是（1+另一非空节点的高度），这一点是与第1题（104.二叉树的最大深度）不一样的。所以后序遍历方法需首先对空节点返回当前depth，再对上述情况进行相应return，最后即为取左，右子树深度最小值的情况。

  1. class Solution {
  2. public:
  3.     int getDepth(TreeNode* cur, int depth) {
  4.         if (cur == nullptr) {
  5.             return depth;
  6.         }
  7.         if (cur->left != nullptr && cur->right == nullptr) {
  8.             return getDepth(cur->left, depth + 1);
  9.         }
  10.         if (cur->left == nullptr && cur->right != nullptr) {
  11.             return getDepth(cur->right, depth + 1);
  12.         }
  13.         return min(getDepth(cur->left, depth + 1), getDepth(cur->right, depth + 1));
  14.     }
  15.     int minDepth(TreeNode* root) {
  16.         return getDepth(root, 0);
  17.     }
  18. };

        前序遍历方法也沿用这一思路（直接使用前两道题题解的写法），使用全局变量res保存结果，递归终止条件为当前节点无左右子节点。因为是取最小值，但depth是随递归的嵌套而·变大的，所以这一题只能在递归终止时更新res。然后在当前节点有左、右子节点的情况下分别进行左、右子节点的递归。

  1. #include<climits>
  2. class Solution {
  3. public:
  4.     int res;
  5.     void getDepth(TreeNode *cur, int depth) {
  6.         if (cur->left == nullptr && cur->right == nullptr) {
  7.             res = min(res, depth);
  8.             return;
  9.         }
  10.         if (cur->left != nullptr) {
  11.             getDepth(cur->left, depth + 1);
  12.         }
  13.         if (cur->right != nullptr) {
  14.             getDepth(cur->right, depth + 1);
  15.         }
  16.         return;
  17.     }
  18.     int minDepth(TreeNode* root) {
  19.         if (root == nullptr) {
  20.             return 0;
  21.         }
  22.         res = INT_MAX;
  23.         getDepth(root, 1);
  24.         return res;
  25.     }
  26. };

        迭代法仍与之前一样，只需要进行提前return即可，提前return的时机是当前节点没有子节点时。

  1. class Solution {
  2. public:
  3.     int minDepth(TreeNode* root) {
  4.         if (root == nullptr) {
  5.             return 0;
  6.         }
  7.         queue<TreeNode*> que;
  8.         que.push(root);
  9.         int depth = 0;
  10.         while (!que.empty()) {
  11.             int size = que.size();
  12.             ++depth;
  13.             for (int i = 0; i < size; ++i) {
  14.                 TreeNode *cur = que.front();
  15.                 que.pop();
  16.                 if (cur->left == nullptr && cur->right == nullptr) {
  17.                     return depth;
  18.                 }
  19.                 if (cur->left) {
  20.                     que.push(cur->left);
  21.                 }
  22.                 if (cur->right) {
  23.                     que.push(cur->right);
  24.                 }
  25.             }
  26.         }
  27.         return depth;
  28.     }
  29. };

         二刷：更简单的写法：

  1. class Solution {
  2. public:
  3.     int minDepth(TreeNode* root) {
  4.         if (root == nullptr) {
  5.             return 0;
  6.         }
  7.         if (root->left == nullptr) {
  8.             return minDepth(root->right) + 1;
  9.         }
  10.         else if (root->right == nullptr) {
  11.             return minDepth(root->left) + 1;
  12.         }
  13.         else {
  14.             return min(minDepth(root->left), minDepth(root->right)) + 1;
  15.         }
  16.     }
  17. };

        第4题（222.完全二叉树的节点个数）的有通用解法和针对完全二叉树的特定解法。

        通用解法的递归解法可以使用后序遍历方式，递归出口为当前节点空时，之后将（1 + 左子树节点数 + 右子树节点数）作为结果返回。

  1. class Solution {
  2. public:
  3.     int countNodes(TreeNode* root) {
  4.         if (root == nullptr) {
  5.             return 0;
  6.         }
  7.         return 1 + countNodes(root->left) + countNodes(root->right);
  8.     }
  9. };

        迭代法也还是沿用层序遍历的模板，只需在内层循环过程中记录节点数。

  1. class Solution {
  2. public:
  3.     int countNodes(TreeNode* root) {
  4.         if (root == nullptr) {
  5.             return 0;
  6.         }
  7.         queue<TreeNode*> que;
  8.         que.push(root);
  9.         int cnt = 0;
  10.         while (!que.empty()) {
  11.             int size = que.size();
  12.             for (int i = 0; i < size; ++i) {
  13.                 ++cnt;
  14.                 TreeNode *cur = que.front();
  15.                 que.pop();
  16.                 if (cur->left) {
  17.                     que.push(cur->left);
  18.                 }
  19.                 if (cur->right) {
  20.                     que.push(cur->right);
  21.                 }
  22.             }
  23.         }
  24.         return cnt;
  25.     }
  26. };

        针对完全二叉树的特定解法需要少量的理论基础。首先，满二叉树的节点个数为2^depth - 1（depth为路径节点数）；其次，完全二叉树分以下2种情况：

  1. 是满二叉树；
  2. 不是满二叉树，但其左、右子树向下递归到一定层数后一定是满二叉树（单个节点的树也是满二叉树）。

        所以针对完全二叉树的特定解法也是递归解法，在满足1时可直接得到其节点个数，而在情况2则递归其左、右子节点，直至满足1为止，然后总结点个数为（1 + 左子树节点数 + 右子树节点数）。所以问题转化为了如何判断一个完全二叉树是否为满二叉树，这里的理论是完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，即最左节点深度等于最右节点深度的话，该完全二叉树就是满二叉树。

  1. class Solution {
  2. public:
  3.     int countNodes(TreeNode* root) {
  4.         if (root == nullptr) {
  5.             return 0;
  6.         }
  7.         TreeNode *left = root->left;
  8.         TreeNode *right = root->right;
  9.         int leftDepth = 0, rightDepth = 0;
  10.         while (left != nullptr) {
  11.             left = left->left;
  12.             leftDepth++;
  13.         }
  14.         while (right != nullptr) {
  15.             right = right->right;
  16.             rightDepth++;
  17.         }
  18.         if (leftDepth == rightDepth) {
  19.             return (2 << leftDepth) - 1;
  20.         }
  21.         return 1 + countNodes(root->left) + countNodes(root->right);
  22.     }
  23. };

代码第19行使用了左移的方法来代替次方计算，可以将“用2 << x代替pow(2, x)”作为一项基本技巧掌握。通用方法的递归和迭代解法时间复杂度都是O(n)，而该针对完全二叉树的特定解法的递归次数是logn，且每次递归中计算左、右子树的最左、最右节点深度，这一步骤时间复杂度也是O(logn)，所以总的算法时间复杂度是O(logn * logn)。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/887657
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号