[C] PTA 6-8 finding the height of binary tree

This problem requires a given height of a binary tree .

Function interface definition ：

int GetHeight( BinTree BT ); 

among BinTree The structure is defined as follows ：

typedef struct TNode *Position; 
typedef Position BinTree; 
struct TNode{ 
    ElementType Data; 
    BinTree Left; 
    BinTree Right; 
}; 

The function is required to return the given binary tree BT Height value of .

Ideas ：

The height of a binary tree is the height of the root node .

The current node height is known = Maximum subtree height +1, So recursively find the left and right child nodes （ Left and right subtrees ） Height is good .

Time complexity ：O(N) N It's the number of knots  

Spatial complexity ：O(1)  Because only three variables are needed to record the height value

int GetHeight( BinTree BT ){
    int hl=0;
    int hr=0;
    int h=0;
    
    if(BT==NULL){
        return 0;
    }
    
    hl=GetHeight(BT->Left);// Find the height of the left subtree 
    hr=(GetHeight(BT->Right));// Find the height of the right subtree 
    
    if(hl>hr){
        h=hl+1;
    }else{
        h=hr+1;
    }
    return h;
}

The following is the assistant who typed blindly because my article was too short ：

Recursion is an easy way to understand .

So is there any other way to solve this problem besides recursion ？

The height of a tree can also be understood as the number of layers . We can try to use the idea of sequence traversal to calculate the height of the tree .

It would be nice if there was a variable in the node structure to record the level of the current node —— EH ,data No, just ？ After all, this problem does not require the output of node data , therefore data You can tamper with it at will

Create and use a queue , The root node is assigned １, Make it into the team ; The left and right children are assigned ２, The team ．．．．．．

namely ： Child node data value = Parent node data value +1, And enter the queue .

Set a int Variable h. Traverse the queue , If you compare h Give to h.

The team + The time complexity of leaving the team ： O(N)

Spatial complexity ：O(N)

...... Yes , Is negative optimization

So recursion is not always bad （ Stand hand ）