7-23 还原二叉树

分数 25

作者 DS课程组

单位 浙江大学

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入格式:

输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出格式:

输出为一个整数，即该二叉树的高度。

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

5

 算法笔记上的代码我是写过不止一遍，浙大陈越讲解这题的时候，我也是去写了一遍的，并且用中序和后序确定一棵二叉树我也是自己练习的了,就在前几天，算法笔记上的一道练习题，用中序和后序得到层次遍历，我也是写了的。今天写这道题的时候，得到一个二叉树的函数，我边界情况还是未能找到，这又是怎么回事呢？自己的学习效率就那么差吗！还是说以前写的都没有真正装在自己的脑袋里。emm，对自己有那么一丢丢小失望了。

但无论任何，我不能放弃；

有志者，事竟成，破釜沉舟，百二秦关终属楚；

苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
与君共勉！跑着跑着就天亮了，当光照进来的时候，你嘴角上扬的角度就是对你最大的回报。

/**
 * 先通过前序遍历和中序遍历，得到后序遍历，即得到一棵确定的二叉树；
 * 然后就可以求得树的高度；
 *
 * 当然树的节点可以要一个 lay 变量存储子树的高度，也可以不要lay变量；
 *
 * 这是不需要 lay变量的程序：
 *  int get_high(BinTree root)
    {
        if(root == NULL)
            return 0;
        else
            return max(get_high(root->l),get_high(root->r)) + 1;
    }
    
    这是需要lay变量的：
    int updateH(BinTree root)
    {
        if(root == NULL)
            return 0;
        else
            return root->lay = max(updateH(root->l),updateH(root->r)) + 1;
    }
    
    其实思想是一样的，换汤不换药；
*/

不要lay 变量

/**
 * 先通过前序遍历和中序遍历，得到后序遍历，即得到一棵确定的二叉树；
 * 然后就可以求得树的高度；
 * 
 * 当然树的节点可以要一个 lay 变量存储子树的高度，也可以不要lay变量；
 * 
 * 这是不需要 lay变量的程序：
 *  int get_high(BinTree root)
    {
        if(root == NULL)
            return 0;
        else
            return max(get_high(root->l),get_high(root->r)) + 1;
    }
    
    这是需要lay变量的：
    int updateH(BinTree root)
    {
        if(root == NULL)
            return 0;
        else
            return root->lay = max(updateH(root->l),updateH(root->r)) + 1;
    }
    
    其实思想是一样的，换汤不换药；
*/

/**
#include <iostream>
#include <algorithm>

using namespace std;

typedef struct TNode* BinTree;

struct TNode
{
    char data;
    BinTree l,r;
    int lay;
    
    TNode()
    {
        l = r = NULL;
        lay = 0;
    }
};

string pre,mid;

BinTree get_beh(int preL,int preR,int midL,int midR)
{
    if(preL > preR) //当不能形成一棵树的时候，返回 NULL
        return NULL;
    BinTree root = new TNode;
    
    int head = pre[preL];
    int idx;
    for(idx=midL;idx<=midR;++idx)
    {
        if(mid[idx] == head)
            break;
    }
    
    int numL = idx - midL;
    root->data = pre[preL];
    root->l = get_beh(preL+1,preL+numL,midL,midL+numL-1);
    root->r = get_beh(preL+numL+1,preR,midL+numL+1,midR);
    return root;
}

int get_high(BinTree root)
{
    if(root == NULL)    //结点为空，返回0；
        return 0;
    else
        return max(get_high(root->l),get_high(root->r)) + 1; 
}       //返回左右孩子高度较高一个的高度加一

int main()
{
    int n;
    cin >> n;
    
    cin >> pre >> mid;
    
    BinTree root = get_beh(0,n-1,0,n-1);
    
    cout << get_high(root) << endl;
    return 0;
}

*/

要lay 变量：

#include <iostream>
#include <algorithm>

using namespace std;

typedef struct TNode* BinTree;

struct TNode
{
    char data;
    BinTree l,r;
    int lay;
    
    TNode()
    {
        l = r = NULL;
        lay = 0;
    }
};

string pre,mid;

BinTree get_beh(int preL,int preR,int midL,int midR)
{
    if(preL > preR)
        return NULL;
    BinTree root = new TNode;
    
    int head = pre[preL];
    int idx;
    for(idx=midL;idx<=midR;++idx)
    {
        if(mid[idx] == head)
            break;
    }
    
    int numL = idx - midL;
    root->data = pre[preL];
    root->l = get_beh(preL+1,preL+numL,midL,midL+numL-1);
    root->r = get_beh(preL+numL+1,preR,midL+numL+1,midR);
    return root;
}

int getHeight(BinTree root)
{
    if(root == NULL)
        return 0;
    else 
        return root->lay;
}

int updateH(BinTree root)
{
    if(root == NULL)
        return 0;
    else
        return root->lay = max(updateH(root->l),updateH(root->r)) + 1;
}

int main()
{
    int n;
    cin >> n;
    
    cin >> pre >> mid;
    
    BinTree root = get_beh(0,n-1,0,n-1);
    
    updateH(root);
    
    cout << getHeight(root) << endl;
    return 0;
}