这是我们算法设计与分析课的一道课后 OJ 题

题目描述

记T为一棵二叉树，树中共有n个节点。

定义根节点的深度为0，其余节点的深度为其父节点的深度加1。T的高度定义为其叶节点深度的最大值。

定义树中任意两点a和b之间的距离为其间最短简单路径的长度。T的直径定义为T中所有点对间距离的最大值。

输入一棵二叉树T，请计算它的高度和直径。

输入

输入共三行。

第一行输入n的值，表示树中结点的总个数。

第二行为树的前序遍历表示，每个节点之间用空格隔开。

第三行为树的中序遍历表示，每个节点之间也用空格隔开。

输出

第一行输出树的高度。
第二行输出树的直径。

样例输入

10
0 1 9 3 8 4 2 7 5 6
3 9 8 1 2 4 0 5 7 6

样例输出

3
5

思路

这道题其实是两道题，第一个部分是根据前序和中序序列重建二叉树，第二个部分是求二叉树的直径。

part1

根据前序序列，我们总是很容易找到根节点，就是 preorder[0], 在中序序列中找到 preorder[0],它将中序序列分成两个部分，左边是左子树的中序序列，右边是右子树的中序序列。这样我们就得到了左右子树的大小，在前序序列中，第 1~leftSize 个元素是左子树的前序序列，剩下的是右子树的前序序列。这样，我们就得到了左右子树的前序序列和中序序列，我们先创建根节点，然后再递归地创建左右子树，就得到整个二叉树。

part2

直径有两种情况，一种是过根节点，一种是不过根节点，不过根节点的情况递归求即可，过根节点的情况就是左子树中最深的点到右子树中最深的点的距离，最后三者取max即可，在过程中要维护每个节点的高度。

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;



struct TreeNode{
    TreeNode* left;
    TreeNode* right;
    int val;
    int height;
    TreeNode(int v){
        val = v;
        left = NULL;
        right = NULL;
        height = 0;
    }
};

TreeNode* construct(vector<int>& preorder, vector<int>& inorder, int l1, int r1, int l2, int r2){
    if(l1 > r1)return NULL;
    if(l1 == r1)return new TreeNode(preorder[l1]);
    TreeNode* root = new TreeNode(preorder[l1]);
    int index = l2;
    while(index <= r2 && inorder[index] != root->val)index ++;
    int leftSize = index - l2;
    root->left = construct(preorder, inorder, l1+1, l1+leftSize, l2, index-1);
    root->right = construct(preorder, inorder, l1+leftSize+1, r1, index+1, r2);
    return root;
}

int diameterOfTree(TreeNode* root){
    if(root == NULL)return 0;
    if(root->left == NULL && root->right == NULL){
        root->height = 0;
        return 0;
    }

    int lres = diameterOfTree(root->left);
    int rres = diameterOfTree(root->right);
    int res = max(lres, rres);
    int d = 0;
    if(root->left != NULL)d += 1 + root->left->height;
    if(root->right != NULL)d += 1 + root->right->height;
    res = max(res, d);
    if(root->left != NULL)root->height = max(root->height, root->left->height + 1);
    if(root->right != NULL)root->height = max(root->height, root->right->height + 1);

    return res;
}

void getInput(vector<int>& preorder, vector<int>& inorder){
    int n;
    scanf("%d", &n);
    preorder.resize(n);
    inorder.resize(n);
    for(int i = 0; i < n; i ++)scanf("%d", &preorder[i]);
    for(int i = 0; i < n; i ++)scanf("%d", &inorder[i]);
}


int main(){
    vector<int> preorder, inorder;

    getInput(preorder, inorder);

    int n = preorder.size();

    TreeNode* root = construct(preorder, inorder, 0, n-1, 0, n-1);

    int res = diameterOfTree(root);

    int height = root->height;


    cout << height << endl;

    cout << res << endl;

    return 0;
}