二叉树高度有关问题

二叉树高度问题

C/C++ code

int CLinkedBitree::Height(CNode* pCurrent) const{    if(pCurrent == NULL)        return -1;    else return Height(pCurrent->pLeft) > Height(pCurrent->pRight) ? 1 + Height(pCurrent->pLeft) : 1 + Height(pCurrent->pRight);}

第一个问题：网上很多程序写为if(pCurrent == NULL) return 0;而我的课本和weki百科："The depth (or height) of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a depth of zero."觉得我是对的。
第二个问题：时间和空间复杂度各是多少，咋算出来的？

谢谢

[解决办法]
1.应该return 0
2.时间和空间复杂度为O(logn)，也即树的高度
[解决办法]
你的不对，返回了-1就是错误的。如果以棵空树，按照你的意思你的树的高度就是-1咯。可是你给的wiki不就是说空树是0么？？时间复杂度好像不是lgn吧？？
[解决办法]
时间复杂度应该是O(n)，
T(n) = 2 * T(n / 2) + 1;
T(0) = 0;
依照主定理，可得T(n) = O(n)

查看更多 下一篇