C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

计算一个二叉树中叶子节点的个数是二叉树的常见问题之一。使用递归或非递归算法都可以实现这个功能，下面我们逐步讲解两种算法的实现过程。

递归算法

递归算法是一种自上而下、分而治之的算法思想。在二叉树中，递归算法的实现也是先计算根节点，再计算左子树和右子树，最终得出结果。

递归计算二叉树叶子节点个数的方法，可以分为三个步骤：

• 如果根节点为空，则叶子节点数量是0。
• 如果根节点的左右节点都为空，则根节点为叶子节点，叶子节点数量是1。
• 如果根节点的左右节点有一个或两个非空，则叶节点数量是左子树叶节点的数量加上右子树叶节点的数量。

下面是递归算法计算二叉树叶节点个数的实现示例：

int countLeafNode(TreeNode* root) {
   if (root == nullptr) {
      return 0;
   }
   if (root->left == nullptr && root->right == nullptr) {
      return 1;
   }
   return countLeafNode(root->left) + countLeafNode(root->right);
}

非递归算法

非递归算法是一种利用数据结构栈或队列进行迭代的算法。与递归算法不同，非递归算法的实现是先计算叶子节点，再计算叶子节点的父节点，一层一层向上计算。

对于二叉树的非递归计算叶节点个数的算法，我们可以使用深度优先遍历实现。具体实现步骤如下：

• 将二叉树的根节点推入栈中。
• 如果栈不为空，弹出一个节点，如果该节点为叶子节点，计数器加1。
• 如果该节点不是叶子节点，则将其右子树推入栈中，然后将其左子树推入栈中。

下面是非递归算法计算二叉树叶节点个数的实现示例：

int countLeafNode(TreeNode* root) {
   if (root == nullptr) {
      return 0;
   }
   stack<TreeNode*> s;
   s.push(root);
   int count = 0;
   while (!s.empty()) {
      TreeNode* node = s.top();
      s.pop();
      if (node->left == nullptr && node->right == nullptr) {
         count++;
      }
      if (node->right != nullptr) {
         s.push(node->right);
      }
      if (node->left != nullptr) {
         s.push(node->left);
      }
   }
   return count;
}

以上就是使用递归和非递归算法分别计算二叉树叶节点个数的完整攻略。