非递归求二叉树的叶结点个数

非递归求二叉树的叶结点个数可以通过栈来实现。具体步骤如下：

1. 定义一个栈，并将根节点压入栈中。

2. 当栈不为空时，弹出栈顶元素，如果该元素是叶子节点，则计数器加1。

3. 如果该元素不是叶子节点，则将其右子节点和左子节点（如果存在）依次压入栈中。

4. 重复执行第2步到第3步，直到栈为空。

以下是该算法的Python代码实现：

def count_leaves(root):
    if not root:
        return 0
    
    count = 0
    stack = [root]
    
    while stack:
        node = stack.pop()
        if not node.left and not node.right:
            count += 1
        else:
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
    
    return count

其中，root是二叉树的根节点，该函数返回二叉树的叶子节点个数。

相关问题

非递归算法求二叉树的叶结点个数C++

可以使用迭代法（非递归算法）来求解二叉树的叶结点个数，具体思路如下：

1.定义一个计数器 count，初始化为0。

2.使用栈来遍历二叉树。首先将根节点入栈。

3.进入循环，当栈不为空时执行以下操作：

- 弹出栈顶元素，如果该元素为叶结点，则将 count 加1。
- 如果该元素有右子树，则将右子树入栈。
- 如果该元素有左子树，则将左子树入栈。

4.遍历结束后，返回 count 值即可。

下面是C++代码实现：

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

其中，TreeNode 表示二叉树的节点。

用非递归算法求二叉树的叶结点个数c

可以使用迭代法（非递归）实现二叉树的叶子节点个数。具体步骤如下：

1. 定义一个栈来存储节点指针。

2. 从根节点开始，将根节点指针入栈。

3. 循环遍历栈中的节点指针，如果该节点是叶子节点，则叶子节点个数加1；否则，将该节点的左右子节点指针分别入栈。

4. 直到栈为空，遍历结束，返回叶子节点个数。

以下是C++代码实现：

int countLeafNode(TreeNode* root) {
    if (root == nullptr) return 0;

    stack<TreeNode*> st;
    st.push(root);
    int count = 0;

    while (!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        if (cur->left == nullptr && cur->right == nullptr) {
            count++;
        } else {
            if (cur->left) st.push(cur->left);
            if (cur->right) st.push(cur->right);
        }
    }
    return count;
}

注：这里假设树节点的定义为 `TreeNode`，包含 `left` 和 `right` 分别表示左右子节点的指针。