This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center。
给定一个完整二叉树的前序遍历，其中每个节点被标记为一个叶节点或一个内部节点，有没有找到树的高度的好算法例如，如果N代表一个内部节点，L代表一个叶，那么给定预序遍历NLNNLLL，高度将是3。
最佳答案
好吧，我忍不住感到很难过，我们把玛蒂留在评论里。我认为他真的不知道从哪里开始，至少已经证明他已经考虑过这个问题。
我们对完整的二叉树了解多少每个节点要么是一个叶，要么有两个子节点。
前序遍历递归地访问根、左子树、右子树。
想想这个问题：在（一个完整的二叉树）的前序遍历中，我们知道什么时候已经耗尽了一个子树？我们将访问它的根，然后是两片叶子（如果它是一片叶子，则仅访问根）。
让我们用一个特殊的结构做一个堆栈：
struct StackNode{
size_t count; //initialize to 0
char nodeType; //'N' or 'L'
};
这个“stacknode”对象将使用“nodeType”变量跟踪我们在预订单遍历中访问的节点类型，该变量应该是清楚的。我们还有一个特殊的计数器'count'，我们初始化为0。
解决方案背后的想法是：
每次遇到“N”时，创建一个StackNode，并将其推到堆栈上。
每次遇到“L”时，创建一个StackNode，并将其推到堆栈上
如果您推送到堆栈上的最后一个节点是“l”，则弹出最后一个节点，然后将stack.top（）的计数增加1
如果stack.top（）的计数为2，则从堆栈中弹出顶部，然后将stack.top（）的计数增加1（重复此操作，直到堆栈为空或停止弹出堆栈）
每次将节点推到堆栈上时，都可以检查树的当前高度。它是堆栈1中的项目数（表示底部的项目是根）。
只要你追踪到迄今为止遇到的最大高度，你就会发现你的树的高度。
让我们看看你的例子：
NLNNLLL堆栈最初为空。
int maxHeight = -1;
处理第一个字符：
N将节点推到堆栈上：
堆栈：类型计数
N，0个
最大高度=0；
处理下一个字符：
L将节点推到堆栈上：
左，0
N，0个
最大高度=1；//（增加1）
最后处理的字符是一个叶，因此pop和increment：
堆栈：
N，1号
最大高度=1；
处理下一个字符：
N将节点推到堆栈上：
N，0个
N，1号
maxHeight=1；//不变
处理下一个字符：
N将节点推到堆栈上：
N，0个
N，0个
N，1号
最大高度=2；//（增加1）
处理下一个字符：
L将节点推到堆栈上：
左，0
N，0个
N，0个
N，1号
maxHeight=3；//递增1
最后一个节点是一个叶，所以pop和increment
堆栈：
N，1号
N，0个
N，1号
maxHeight=3；//未更改
处理下一个字符：
L将节点推到堆栈上：
左，0
N，1号
N，0个
N，1号
maxHeight=3；//未更改
最后一个节点是一个叶，因此pop和increment：
N，2个
N，0个
N，1号
顶部节点的计数为2，因此pop和increment：
N，1号
N，1号
处理下一个节点：
L将节点推到堆栈上：
左，0
N，1号
N，1号
maxHeight=3；//未更改
最后一个节点是一个叶，因此pop和increment：
N，2个
N，1号
顶部节点的计数为2，因此pop和increment：
N，2个
顶部节点的计数为2，因此pop和increment：
(empty stack), finished
maxHeight = 3; //the maximum height discovered during a preorder of a full binary tree
09-25 20:55