用非递归算法求二叉树的叶结点个数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` 分别表示左右子节点的指针。

相关问题

请用c++的非递归方法实现求二叉树的叶结点个数

以下是使用C++的非递归方法实现求二叉树的叶节点个数的代码：

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

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

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    cout << countLeafNodes(root) << endl; // Output: 3
    return 0;
}

这里使用了栈来实现非递归遍历二叉树，对于每个节点，如果它没有左子树和右子树，那么它就是叶节点，计数器加1。然后将它的左子节点和右子节点（如果存在）压入栈中，继续遍历。最后返回计数器的值即可。

编写程序实现求二叉树的结点个数，叶结点个数，二叉树的高度及交换二叉树所有左右子树的操作

要编写程序实现二叉树的节点计数、叶节点计数、高度计算以及交换子树的操作，可以使用递归的方式来进行。下面是相关的代码实现：

### 1. 求二叉树的节点数

int countNodes(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return 1 + countNodes(node->left) + countNodes(node->right);
}

// 示例：
TreeNode* root; // 树的根节点
cout << "Total nodes: " << countNodes(root) << endl;

### 2. 求二叉树的叶节点数

int countLeaves(TreeNode* node) {
    if (node == nullptr || (node->left == nullptr && node->right == nullptr)) {
        return 1;
    }
    return countLeaves(node->left) + countLeaves(node->right);
}

// 示例：
cout << "Total leaves: " << countLeaves(root) << endl;

### 3. 求二叉树的高度（这里假设二叉树是平衡的，对于非平衡的树，需要采用其他复杂算法如Kahn算法）

int height(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);
    return max(leftHeight, rightHeight) + 1;
}

// 示例：
cout << "Tree height: " << height(root) << endl;

### 4. 交换二叉树的所有左右子树
这是一个递归操作，首先检查节点是否为空，然后递归处理左右子树，并在必要时交换子节点。

void swapChildren(TreeNode* &node) {
    if (node != nullptr) {
        std::swap(node->left, node->right);
        swapChildren(node->left);
        swapChildren(node->right);
    }
}

// 示例：
swapChildren(root);