C++如何求解二叉树深度？ |21xrx.com

C++如何求解二叉树深度？

2023-07-01 03:26:06 深夜i 53 0

C++ 二叉树深度求解

在计算机科学中，二叉树是一种常用的数据结构，它由一个根节点和最多两个子节点组成。在许多算法中，需要计算二叉树的深度。在C++中，你可以用递归算法和非递归算法两种方式来求解二叉树深度。

递归算法是一种常用的方法，它通过自身的调用来完成计算。在二叉树的深度计算中，我们可以编写一个递归函数，当进入一个节点时，我们将其左右子树的深度分别计算出来，然后返回最大值加1，作为当前节点的深度。这个方法的递归结束条件是节点为NULL，即到达了叶子节点。C++中代码的实现如下：

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

非递归算法是另外一种方法，它不使用递归，而是使用一个栈来模拟递归过程。我们按照层次遍历的顺序来计算每一层的深度，每遍历完一层就将深度加1。C++中代码的实现如下：

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

以上两种方法都可以用来计算二叉树的深度，其中递归算法比较简单，但是有可能会出现栈溢出的情况，而非递归算法则需要使用额外的空间来维护栈。在实际应用中，我们可以根据具体问题的场景来选择不同的算法。

上一篇: idea打包java可执行jar包

下一篇: C++菜鸟编程入门指南

评论区

相似文章