二叉树

Question

关于混乱高度假设我的树是这个样子

 5 
/\ 
    1 8 
    /\ 
    6 9 

我写了一个程序来找到这个高度。

 65 int height(const TNODE* root) {                                                   
66   if (root == NULL) {                                                    
67     return 0;                                                     
68   } else {                                                       
69     int lDepth = height(root->left);                                               
70     int rDepth = height(root->right);                                               
71     if (lDepth > rDepth) {                                                  
72       return (lDepth + 1);                                                
73     } else {                                                     
74       return (rDepth + 1);                                                
75     }                                                       
76                                                           
77   }                                                         
78 } 

运行此方法会为上面的树打印3。但是高度不应该是2，因为那是从根到最远叶子的边缘数量？我在网上搜索，我得到了矛盾的信息。有人会说我上面的树高3，而其他人说2。

那么我的树上面应该有多高，为什么？

我的方法正确吗？

Answer 1

术语“高度”在这里有点过于笼统。根据精确的定义，2或3可能是正确的答案。

例如，如果我声明树的高度是它包含的“水平”的数量，则3是正确的答案。但是，如果我声明树的高度是跨越边界以达到树叶的最大数量，而不会超过一次边（即没有反向跟踪），那么2是正确的答案。

根据我的经验，更常见的答案是3.树有3个级别。只有根节点的树的高度为1.我宁愿这样做，因为空树的高度为0.

Answer 2

只是关于风格的建议。

int height(const TNODE* root) {                                                   
    if (root == NULL) {                                                    
     return 0;                                                     
    } else {                                                       
     int lDepth = height(root->left);                                               
     int rDepth = height(root->right); 
     return max (lDepth, rDepth) + 1;                                                 
    }                                                         
    }