在今天的面试中，我被问到了二叉树深度的计算。
一听到这个问题，第一反应就是大学被推翻的基本数据结构问题。
但是我毕业三年了，没写算法，就出手了。 但是，不能说出生后就只对面试官说想法。 于是，果然没想就马上拿起笔，开始写了起来。 这是基本数据结构的主题。
首先马上写了二叉树结构。
publicclassbinarytree { binarytreelchild，rChild； int value； }一写起来，马上就有了感觉。 趁势写了计算方法
publicintcomputetreedepth (binarytreebinarytree ) binary tree.lchild==nullbinarytree.rchild==null { return1} intr depth=computetreedepth (binary tree.rchild )； returnmath.max(LDepth，rDepth )； }然后给面试官看了。
面试官有没有感觉到我有什么地方不对劲？ 呃，只是因为久违地写了算法的问题，就连这个基本的深入计算也犯了简单的错误。 更可悲的是，在当时紧张的环境下，我没有发现任何问题。 后来，经过面试官的注意，终于变了。
publicintcomputetreedepth (binarytreebinarytree ) if ) binary tree==null { return 0； } if (binary tree.lchild==nullbinarytree.rchild==null ) { return 1； } intl depth=computetreedepth (binary tree.lchild ) 1； intr depth=computetreedepth (binary tree.rchild ) 1； returnmath.max(LDepth，rDepth )； 这时，在我心中有一万人对自己无言以对，在面试中犯了这么大的错误。 (但是，平时毕业后很少深入写算法问题，所以今后要小心。 ）
此时，面试官说这是递归实现，并写下非递归实现。
那时，默默无言的我突然非递归地实现了。 然后，仔细想想，很简单。 然后，我开始写了。 写了之后才注意到，情况好像没有我想象的那么简单。 随着时间的流逝，我的心异常紧张，结果那几分钟想不到。 我现在真的深深地鄙视自己。 不管出于什么原因让我当时的大脑短路，最终，我都没能写出非递归的实现。 之后，面试官委婉地告诉我要考虑这个问题。
总结：
问题：自己太想表达自己了，自己的想法太紧凑了，反而限制了我的思考，这个简单的问题也写了漏洞，甚至连非递归的实现都没有写在最后。
对自己的想法：
1 .作为程序猴，平时要锻炼自己的算法编写习惯，多思考。 只有这样才能在面试中很好地控制算法问题。
2 .面试的时候，要保持心情平静。 不要急躁，给自己惹各种临时小问题。 因为对方只看结果。
我回来了。 我自己重写了二叉树深度计算的实现。 果然很简单。 记录下来吧。 我觉得自己成为了前进道路上的障碍，每次自己总结都想让自己进步。
多思考，多学习，静下心来，面对新技术、新思路。
在下面贴上代码
二叉树深度计算的递归实现：
publicintcomputetreedepth (binarytreebinarytree ) if ) binary tree==null { return 0； } return math.max (computetreedepth (binary tree.lchild )，computetreedepth (binary tree.rchild ) ) 1； }二叉树深度计算的非递归实现：
首先我认为是直接扫描，如果是直接扫描的话自然有两种想法。 广度优先和深度优先。
首先广度优先，遍历下一个层次意味着上面的层次已经被遍历，通过先进先出、队列来实现：
publicintcomputetreedepth (binarytreebinarytree )//实例化队列queuebinarytreemvisitlist=new linked list； 二进制树tmp； int depth=0，lengthTmp； if(Binar )
yTree == null){ //根为空，直接返回0 return 0; } //将根加入队列 mVisitList.offer(binaryTree); while (!mVisitList.isEmpty()){ //只要队列不为空，说明新的一层数据不为空，且已经加到队列，深度+1 depth ++; //遍历该层到所有数据，将他们出队，并附带把所有下一层到数据都加进来(如果有的话) lengthTmp = mVisitList.size(); while (lengthTmp -- > 0){ tmp = mVisitList.poll(); if(tmp.lChild != null){ mVisitList.offer(tmp.lChild); } if(tmp.rChild != null){ mVisitList.offer(tmp.rChild); } } } return depth; }然后深度优先，因为是深度遍历那肯定是先进后出，采用栈实现，然后遍历思路是先遍历当前节点的左子树，没有左子树到情况在遍历右子树：
public int computeTreeDepth(BinaryTree binaryTree){ //实例化栈 Stack<BinaryTree> mVisitList = new Stack<>(); BinaryTree tmp = binaryTree; int depth = 0;//遍历过程中到最大深度 while (tmp != null){ if(tmp.lChild != null || tmp.rChild != null){ //如果有子树，将当前节点入栈，且更新最大深度 mVisitList.push(tmp); depth = Math.max(depth, mVisitList.size()); //因为是左子树优先，所以深度遍历下一个子节点的时候，优先左子树 tmp = tmp.lChild != null ? tmp.lChild : tmp.rChild; continue; } //当前节点没有子树，直接更新最大深度（访问到当前节点到深度是栈的深度+1） depth = Math.max(depth, mVisitList.size() + 1); //此时回溯去找右子树 while (!mVisitList.isEmpty()){ if(mVisitList.peek().rChild != null && mVisitList.peek().rChild != tmp){ //如果栈顶节点的右子树不为空，且栈顶节点的右子树不等于正在访问的节点，访问右子树 tmp = mVisitList.peek().rChild; break; } //说明当前栈顶节点的右子树为空，直接出栈，继续回溯 // 且要更新当前节点，用于记录当前正在回溯的节点，避免死循环回溯 tmp = mVisitList.pop(); } } return depth; }好了，上面就是二叉树的实现，自己写了几个测试用例没出现问题。但是不能保证完全没问题，有问题的话或者可以优化的欢迎留言交流，一起学习进步。