求二叉树高度的非递归算法

可以使用层次遍历的方式求解二叉树的高度，具体实现如下：

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

这个算法的时间复杂度是 O(n)，其中 n 是二叉树的节点数。

相关问题

求二叉树高度的递归和非递归算法

二叉树高度的递归算法可以通过递归遍历左右子树来求得，具体实现可以参考以下代码：

public int height(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

二叉树高度的非递归算法可以使用层序遍历的方式来求得，具体实现可以参考以下代码：

public int height(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int height = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        height++;
    }
    return height;
}

用C++语言实现 实验内容 1．输入字符序列，建立二叉链表。 2．中序遍历二叉树:递归算法。 3．中序遍历二叉树:非递归算法。 4.先序遍历二叉树 5.后序遍历二叉树 4．求二叉树的高度 。 5．求二叉树的叶子个数。 6．编写一个主函数,调试上述算法。

好的，下面是一个用C++语言实现二叉树相关操作的完整代码，包括建立二叉链表、中序遍历（递归和非递归）、先序遍历、后序遍历、求二叉树高度和求二叉树叶子个数。

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

// 定义二叉树节点结构
struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

// 建立二叉链表
TreeNode* createTree() {
    char val;
    cin >> val;
    if (val == '#') return nullptr;
    TreeNode* node = new TreeNode(val);
    node->left = createTree();
    node->right = createTree();
    return node;
}

// 中序遍历二叉树:递归算法
void inorderTraversalRecursive(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversalRecursive(root->left);
    cout << root->data << " ";
    inorderTraversalRecursive(root->right);
}

// 中序遍历二叉树:非递归算法
void inorderTraversalIterative(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root;
    while (current != nullptr || !s.empty()) {
        while (current != nullptr) {
            s.push(current);
            current = current->left;
        }
        current = s.top();
        s.pop();
        cout << current->data << " ";
        current = current->right;
    }
}

// 先序遍历二叉树
void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->data << " ";
}

// 求二叉树的高度
int treeHeight(TreeNode* root) {
    if (root == nullptr) return 0;
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

// 求二叉树的叶子个数
int countLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

// 编写一个主函数,调试上述算法
int main() {
    cout << "请输入二叉树的节点（使用#表示空节点）: ";
    TreeNode* root = createTree();
    
    cout << "中序遍历（递归）: ";
    inorderTraversalRecursive(root);
    cout << endl;
    
    cout << "中序遍历（非递归）: ";
    inorderTraversalIterative(root);
    cout << endl;
    
    cout << "先序遍历: ";
    preorderTraversal(root);
    cout << endl;
    
    cout << "后序遍历: ";
    postorderTraversal(root);
    cout << endl;
    
    cout << "二叉树的高度: " << treeHeight(root) << endl;
    
    cout << "二叉树的叶子个数: " << countLeaves(root) << endl;
    
    return 0;
}