尝试不同方法求二叉树的深度：
1.depth1，递归计算二叉树的深度，根结点的深度=max（左子树的深度，右子树的深度） + 1。
2.depth2，访问左结点，如有右结点则压栈1，同时把右结点的深度压栈2，没有左结点时表示该次遍历完成，记录深度；从栈1取出结点，栈2取出该结点的深度，再次遍历。
3.depth3，利用层序遍历的思想，每完成一层的遍历就给一个标记。
package com.devchao.tree;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;public class BinaryTree { public static void main(String[] args) { Node n15 = new Node(15, null, null); Node n14 = new Node(14, n15, null); Node n13 = new Node(13, null, n14); Node n12 = new Node(12, n13, null); Node n11 = new Node(11, null, n12); Node n5 = new Node(5, null, null); Node n6 = new Node(6, null, null); Node n8 = new Node(8, null, null); Node n9 = new Node(9, n11, null); Node n10 = new Node(10, null, null); Node n7 = new Node(7, n8, null); Node n4 = new Node(4, n6, n7); Node n3 = new Node(3, null, n5); Node n2 = new Node(2, n9, n10); Node n1 = new Node(1, n3, n4); Node root = new Node(0, n1, n2); System.out.println(depth3(root)); } public static int depth1(Node root){ int dep1 = 1, dep2 = 1; if(root.left != null) { dep1 = dep1 + depth1(root.left); } if(root.right != null) { dep2 = dep2 + depth1(root.right); } System.out.println(root.data + " " + dep1 + " " + dep2); return dep1 >= dep2 ? dep1 : dep2; } public static int depth2(Node root){ int dep = 1, tempDep = 1; Stack q = new Stack (); Stack dq = new Stack (); Node node = root; while(node != null || !q.isEmpty()) { if(node == null) { node = q.pop(); dep = dep < tempDep ? tempDep : dep; tempDep = dq.pop(); } if(node.right != null) { dq.add(tempDep + 1); q.add(node.right); } if(node.left != null) { tempDep = tempDep + 1; } node = node.left; } return dep; } public static int depth3(Node root){ int dep = 0, tempTag = 0; Queue queue = new LinkedList<>(); queue.add(root); Queue tagQueue = new LinkedList<>(); tagQueue.add(1); while(!queue.isEmpty()) { root = queue.poll(); if(root.left != null) { queue.add(root.left); tagQueue.add(0); } if(root.right != null) { queue.add(root.right); tagQueue.add(0); } tempTag = tagQueue.poll(); if(tempTag == 1) { dep = dep + 1; if(!tagQueue.isEmpty()) { tagQueue.remove(); tagQueue.add(1); } } } return dep; } static class Node { public int data; public Node left; public Node right; public Node(int data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } }}