Question

用非递归的算法求给定二叉树的高度？？？递归的已有

Answer 1

先一层一层的遍历二叉树 用一个辅助的数据结构队列
队列！ 注意 这个很重要
队首放节点 队尾取出节点
比如：根节点放入队列 （开始只有这个一个节点在队列中）
然后呢 从队尾取出这个根节点 然后打散 把他的左右孩子放入对首（这时候有2个节点 也就是二叉树的第二层）
之后从队伍里取出这2个节点 打散 之后队伍里应该是 二叉树第三层的4个节点
。。。。。
这样就把二叉树层次遍历了
因为有些节点没有孩子节点 也就是叶子
这个队列中的节点 逐渐会越来越少
最后一个取出队列的节点 的深度也就是二叉树的高度

所以求二叉树的高度 就用这种层进性遍历 每次把节点放入队列中时 也把他的深度 和节点的指针一起放入 取出一个节点 打散的时候 注意他的子节点的度是他父节点的+1 就ok