编写算法求二叉树的高度(需预先创建符合要求的二叉树)

以下是求二叉树高度的算法：

# 定义二叉树节点
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 求二叉树高度的函数
def get_height(root):
    if root is None:
        return 0
    left_height = get_height(root.left)
    right_height = get_height(root.right)
    return max(left_height, right_height) + 1

其中，`TreeNode` 是二叉树节点的定义，`get_height` 函数的参数为二叉树的根节点，返回二叉树的高度。

具体实现思路是，如果当前节点为空，则返回高度 0；否则，分别递归求解左右子树的高度，并返回左右子树高度的最大值加上 1。

相关问题

用C++编写建立二叉树，层序、先序遍历 1、问题描述 要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数； 请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。

1、存储结构

二叉树的存储结构有两种：顺序存储和链式存储。顺序存储需要预先确定二叉树的深度，而链式存储结构则可以不用考虑深度，因此本题使用链式存储结构。

定义二叉树节点结构体如下：

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

2、基本算法

建立二叉树的基本算法是递归，递归结束的条件是节点为空或者输入结束标志。输入函数可以先输入节点值，然后递归输入左右子树。输出层序遍历序列的函数可以使用队列进行实现，先将根节点入队，然后每次出队一个节点，将其左右子节点入队，直到队列为空。输出先序遍历序列的函数可以按照根节点、左子树、右子树的顺序递归输出。

3、源程序

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

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

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

void levelOrderTraversal(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
    }
}

void preorderTraversal(TreeNode* root) {
    if (root) {
        cout << root->val << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

int main() {
    TreeNode* root = createTree();
    cout << "层序遍历序列：" << endl;
    levelOrderTraversal(root);
    cout << endl;
    cout << "先序遍历序列：" << endl;
    preorderTraversal(root);
    cout << endl;
    return 0;
}

4、测试数据和结果

输入：

1 2 -1 -1 3 4 -1 -1 5 -1 -1

输出：

层序遍历序列：
1 2 3 4 5
先序遍历序列：
1 2 3 4 5

5、时间复杂度

建立二叉树的时间复杂度为 O(n)，其中 n 为节点个数。层序遍历的时间复杂度为 O(n)，先序遍历的时间复杂度也为 O(n)。

6、改进方法

可以使用非递归的方式实现先序遍历、中序遍历和后序遍历，具体实现可以使用栈来辅助。

设二叉树以二叉链表形式存放，用类C语言设计非递归算法判断一棵根结点为T的二叉树是否为二叉排序树。不使用栈，并且有详细注释

非递归算法判断一棵根结点为T的二叉树是否为二叉排序树，可以使用中序遍历的方式实现。由于二叉排序树的中序遍历结果是一个有序序列，因此只需要在中序遍历时判断当前节点的值是否小于等于前一个节点的值，即可判断二叉树是否为二叉排序树。

具体实现步骤如下：

1. 定义一个指针p指向当前节点，一个指针pre指向前一个节点，初始值为NULL。

2. 对于每个节点，先将其左子树中的所有节点入栈，直到左子树为空。

3. 弹出栈顶元素，即为当前节点，判断当前节点的值是否小于等于前一个节点的值，如果是，则不是二叉排序树；如果不是，则将前一个节点指针pre指向当前节点。

4. 将当前节点的右子树中的所有节点入栈，重复步骤2和3，直到所有节点都被遍历。

代码实现如下：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

int isBST(TreeNode* root) {
    TreeNode* p = root;     // 当前节点指针
    TreeNode* pre = NULL;   // 前一个节点指针
    int flag = 1;           // 是否为二叉排序树的标志

    while (p != NULL) {
        // 将左子树中的所有节点入栈
        while (p != NULL) {
            // 将当前节点入栈
            // 这里用链表的方式实现栈，栈顶元素为p，栈顶指针为next
            next = (struct ListNode*)malloc(sizeof(struct ListNode));
            next->val = p;
            next->next = stack;
            stack = next;
            p = p->left;
        }

        // 弹出栈顶元素，即为当前节点
        p = stack->val;
        stack = stack->next;

        // 判断当前节点的值是否小于等于前一个节点的值
        if (pre != NULL && p->val <= pre->val) {
            flag = 0;
            break;
        }

        // 将前一个节点指针pre指向当前节点
        pre = p;

        // 将右子树中的所有节点入栈
        p = p->right;
    }

    return flag;
}

注意：这里使用了链表实现栈，栈顶元素为p，栈顶指针为next。这样可以避免使用数组实现栈时需要预先确定栈的大小的问题。