力扣题目链接 有如下图二叉树 
前序遍历的规则：根结点 —> 左子树 —> 右子树 或者 currentNode–>currentNode.left–>currentNode.right 所以对应的打印顺序为：a b d e g h c f。 所以递归的算法代码很好写：
public void dlr(Node currentNode) {
if(currentNode==null) {
return;
}
String value = currentNode.value;
System.out.print(" "+value);
//遍历左孩子
Node left = currentNode.left;
dlr(left);
//访问右孩子
Node right = currentNode.right;
dlr(right);
}
用递归思路还是很简单的，如果不用递归的话，就需要用到栈结构，前序遍历用栈来表示的话，整体思路如下： 1）当前访问的是那一个节点：currentNode，那么先获取currentNode的值，然后将currentNode放入栈中。此时currentNode遍历完毕，根据前序遍历的规则，现在即将访问的节点就是currentNode.left .所以此时currentNode= currentNode.left; 2)判断此时currentNode是否是null，如果是null,则弹出栈顶的节点node,同时将currentNode== currentNode.right;如果不为null的话，则重复1（也就是再来一次循环).直到currentNode!= null || !stack.isEmpty()结束循环条件
public List preorderTraversal(TreeNode root) {
List result = new ArrayList();
LinkedList stack = new LinkedList();
TreeNode currentNode = root;
while(currentNode!=null||!stack.isEmpty()) {
if(currentNode!=null) {
stack.push(currentNode);
//先访问根节点
result.add(currentNode.val);
//在访问左孩子
currentNode = currentNode.left;
}else {
//最后访问右孩子
currentNode = stack.pop().right;
}
}
return result;
}
因为先序遍历先访问的是根节点，在二叉树中任意一个节点都可能是根节点，所以在当前节点入栈的时候就需要对其访问，因为该节点也可能拥有自己的左右孩子，也就是说该节点也可能是根节点，所以前序遍历的特点就是：在入栈的时候对当前节点进行遍历（操作）。 需要注意什么时候才出栈/ 用图片来示意上述过程如下： 
力扣题链接 中序遍历的规则：左子树—> 根结点 —> 右子树 中序结果：d b g e h a c f 递归的方法就不写了，很简单。因为中序遍历，先访问的是左孩子，在二叉树中任意一个节点都可能有左孩子，所以对当前节点入栈的时候不能进行访问操作，在出栈的时候进行访问操作。其入栈和出栈操作跟的顺序跟先序遍历一样，只不过访问节点的顺序不一样.需要注意什么时候才出栈.
public List inorderTraversal(TreeNode root) {
List result = new ArrayList();
LinkedList stack = new LinkedList();
TreeNode currentNode = root;
while(currentNode!=null||!stack.isEmpty()) {
if(currentNode!=null) {
stack.push(currentNode);
currentNode = currentNode.left;
}else {
TreeNode node = stack.pop();
result.add(node.val);
currentNode = node.right;
}
}
return result;
}
用图来描述中序遍历如下图： 
前序遍历和中序遍历的特点：入栈顺序和出栈顺序完全一样，但是访问的时机不一样
二叉树的层序遍历：
层次遍历：a b c d e f g h
二叉树的层序遍历思想最简单，之所以说简单是因为工作这么多年很久没用过二叉树了，也就是在大学的时候学过相关知识，居然分分钟写出来了，令我感觉意外。用一个队列就搞定了，核心思想就是在一个节点出队的时候，将其左右孩子节点入队，直到队列为空。 
比如上图，现将a入队，然后出队的时候将其左右节点b c 入队。但b出队的时候将b的左右节点d ,e入队；循环即可。
public List LevelOrder(TreeNode node) {
List result = new ArrayList();
Queue queue = new LinkedList();
queue.offer(node);
while(!queue.isEmpty()) {
//出队
TreeNode currentNode = queue.poll();
result.add(currentNode.value);
//左孩子节点入队
TreeNode left = currentNode.left;
if(left!=null) {
queue.offer(left);
}
//右孩子节点入队
TreeNode right = currentNode.right;
if(right!=null) {
queue.offer(right);
}
}
return result;
}
上述方法返回的list的size就是二叉树的节点总数。
层序遍历的引深：比如我想要如下遍历规则，这也是力扣的一道题：
[
[a],
[b, c],
[d,e,f]
[g, h],
]
只需要对层序遍历做简单的修改就可以，其实规律也很简单:当某层节点都出队的时候，队列中的剩下节点的肯定是下一层的所有节点
比如a出队：队列中就剩下 b c： 
当b 和 c都出队的时候，确切的说当c出队的时候：那么队列中就剩下 d e f： 
所以对层序遍历稍作修改，这个题就做出来了：
public List levelOrder2(TreeNode root) {
if(root==null){
return null;
}
List result = new ArrayList();
//先根节点入队
Queue queue= new LinkedList();
queue.add(root);
while(!queue.isEmpty()){
//队列中节点个数，确切地说是当前层的节点个数
int size = queue.size();
List currentLevel = new ArrayList(size);
//当size==0的时候，当前某层的节点全部出队完毕
while(size>0){
//出队一个
TreeNode currentNode = queue.poll();
size--;
currentLevel.add(currentNode.value);
//左孩子节点入队
TreeNode left = currentNode.left;
if(left!=null) {
queue.offer(left);
}
//右孩子节点入队
TreeNode right = currentNode.right;
if(right!=null) {
queue.offer(right);
}
}//end while：当前层出队完毕
result.add(currentLevel);
}//end while
return result;
}
二叉树的最大深度
注意，该方法返回的list集合的size就是二叉树的最大深度，其实上面的代码可以稍作修改一下就得到了一个效率不高的求最大深度的算法：
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
Queue queue = new LinkedList();
queue.offer(root);
int deep = 0;
while(!queue.isEmpty()){
int size = queue.size();
while(size>0){
size--;
TreeNode node = queue.poll();
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
//访问完了一层
if(size==0){
deep++;
}
}
return deep;
}
当然这里可以换另外一个思路,用递归来进行解决，力扣题目链接：
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}else {
//int leftDepth = maxDepth(root.left)+1;
//int rightDepth = maxDepth(root.right)+1;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth)+1;
}
}
其实算法思路也很好理解：对于一个二叉树来说最深的节点要么在树的左子树上，要么是在二叉树右子树上，最深的当然要取左右子数深度最大的的那个子树了，至于为什么加1，那就更好理解了，对于二叉树来说，只要节点!=null（可能是左节点也可能是右节点），那么除了根节点之外，该节点必有根节点！那么对于这个节点的根节点来说，根节点的深度就是以1为基准的，再加上该根节点的左右子节点构成的最大子树深度，就是本题的返回值。
其递归执行流程可以参考下图： 
比如对于d节点来说，它没有左右节点，所以其深度返回的是0；但是这个节点肯定有父节点c,所以此时c的深度就是return 0+1.其余的同理分析即可。
有递归算法，对象的力扣也提供了了一个非递归算法，算法解题思路很巧妙，先看下图：
每个节点的红色数据就是代表当前节点所在的深度，比如根节点的深度是1，第二层节点的深度都是2，一次类推，下一层节点所在的深度，是上一层节点深度的值+1为了记录各个节点的层级关系，提供了一个Pair类：
/**
* @param Key代表及节点TreeNode对象，
* @param 当前节点的深度
*/
public class Pair implements Serializable {
// Key代表及节点TreeNode对象，
private K key;
//当前节点的深度
private V value;
public K getKey() {
return key;
}
}
所以完整的代码就如下所示：
public int maxDepth4(TreeNode root) {
// key 是节点，value是深度
Queue stack = new LinkedList();
if (root != null) {
stack.add(new Pair(root, 1));
}
int depth = 0;
//当前出站的节点
TreeNode topNode;
while (!stack.isEmpty()) {
// 当前及诶单出站
Pair current = stack.poll();
topNode = current.getKey();
// 获取当前节点的深度值
int current_depth = current.getValue();
// 取深度值最大的那个值
depth = Math.max(depth, current_depth);
//下一层的深度值
int nextLevelDepth = current_depth + 1;
// 把左节点入队，左节点的深度值是current_depth+1
if (topNode.left != null) {
stack.add(new Pair(topNode.left, nextLevelDepth));
}
if (topNode.right != null) {
// 把右节点入队，左节点的深度值是current_depth+1
stack.add(new Pair(topNode.right,nextLevelDepth));
}
}
return depth;
}
