2.1、前序遍历
  首先访问根节点，然后遍历左子树，最后遍历右子树。
2.2、训练
144. 二叉树的前序遍历

589. N叉树的前序遍历

572. 另一个树的子树

1.前序遍历
    前序遍历（DLR，lchild,data,rchild），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
若二叉树为空则结束返回，否则：
（1）访问根结点。
（2）前序遍历左子树。
（3）前序遍历右子树 。
前序遍历
需要注意的是：遍历左右子树时仍然采用前序遍历方法。
如右图所示二叉树
前序遍历结果：ABDECF
已知后序遍历和中序遍历，就能确定前序遍历。
    其实在遍历二叉树的时候有三次遍历， 比如前序遍历：A->B->D->D(D左子节点并返回到D)->D(D右子节点并返回到D)->B->E->E(左)->E(右)->->B->A->C->F->F(左)->F(右)->C->C(右)，所以可以用栈结构，把遍历到的节点压进栈，没子节点时再出栈。也可以用递归的方式，递归的输出当前节点，然后递归的输出左子节点，最后递归的输出右子节点。直接看代码更能理解：
package test;
//前序遍历的递归实现与非递归实现
import java.util.Stack;
public class Test 
{
	public static void main(String[] args)
	{
		TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
		for(int i = 0; i < 10; i++)
		{
			node[i] = new TreeNode(i);
		}
		for(int i = 0; i < 10; i++)
		{
			if(i*2+1 < 10)
				node[i].left = node[i*2+1];
			if(i*2+2 < 10)
				node[i].right = node[i*2+2];
		}
		
		preOrderRe(node[0]);
	}
	
	public static void preOrderRe(TreeNode biTree)
	{//递归实现
		System.out.println(biTree.value);
		TreeNode leftTree = biTree.left;
		if(leftTree != null)
		{
			preOrderRe(leftTree);
		}
		TreeNode rightTree = biTree.right;
		if(rightTree != null)
		{
			preOrderRe(rightTree);
		}
	}
	
	public static void preOrder(TreeNode biTree)
	{//非递归实现
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while(biTree != null || !stack.isEmpty())
		{
			while(biTree != null)
			{
				System.out.println(biTree.value);
				stack.push(biTree);
				biTree = biTree.left;
			}
			if(!stack.isEmpty())
			{
				biTree = stack.pop();
				biTree = biTree.right;
			}
		}
	}
}

class TreeNode//节点结构
{
	int value;
	TreeNode left;
	TreeNode right;
	
	TreeNode(int value)
	{
		this.value = value;
	}
}




2.中序遍历
中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，先左后根再右。巧记：左根右。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树
若二叉树为空则结束返回，
否则：

　　
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
如右图所示二叉树
中序遍历结果：DBEAFC

import java.util.Stack;
public class Test 
{
	public static void main(String[] args)
	{
		TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
		for(int i = 0; i < 10; i++)
		{
			node[i] = new TreeNode(i);
		}
		for(int i = 0; i < 10; i++)
		{
			if(i*2+1 < 10)
				node[i].left = node[i*2+1];
			if(i*2+2 < 10)
				node[i].right = node[i*2+2];
		}
		
		midOrderRe(node[0]);
		System.out.println();
		midOrder(node[0]);
	}
	
	public static void midOrderRe(TreeNode biTree)
	{//中序遍历递归实现
		if(biTree == null)
			return;
		else
		{
			midOrderRe(biTree.left);
			System.out.println(biTree.value);
			midOrderRe(biTree.right);
		}
	}
	
	
	public static void midOrder(TreeNode biTree)
	{//中序遍历费递归实现
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while(biTree != null || !stack.isEmpty())
		{
			while(biTree != null)
			{
				stack.push(biTree);
				biTree = biTree.left;
			}
			if(!stack.isEmpty())
			{
				biTree = stack.pop();
				System.out.println(biTree.value);
				biTree = biTree.right;
			}
		}
	}
}

class TreeNode//节点结构
{
	int value;
	TreeNode left;
	TreeNode right;
	
	TreeNode(int value)
	{
		this.value = value;
	}
}




3.后序遍历（难点）
后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根。巧记：左右根。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：
若二叉树为空则结束返回，
否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点
如右图所示二叉树
后序遍历结果：DEBFCA
已知前序遍历和中序遍历，就能确定后序遍历。
算法核心思想：
    首先要搞清楚先序、中序、后序的非递归算法共同之处：用栈来保存先前走过的路径，以便可以在访问完子树后,可以利用栈中的信息,回退到当前节点的双亲节点,进行下一步操作。
    后序遍历的非递归算法是三种顺序中最复杂的，原因在于，后序遍历是先访问左、右子树,再访问根节点，而在非递归算法中，利用栈回退到时，并不知道是从左子树回退到根节点，还是从右子树回退到根节点，如果从左子树回退到根节点，此时就应该去访问右子树，而如果从右子树回退到根节点，此时就应该访问根节点。所以相比前序和后序，必须得在压栈时添加信息，以便在退栈时可以知道是从左子树返回，还是从右子树返回进而决定下一步的操作。

import java.util.Stack;
public class Test 
{
	public static void main(String[] args)
	{
		TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
		for(int i = 0; i < 10; i++)
		{
			node[i] = new TreeNode(i);
		}
		for(int i = 0; i < 10; i++)
		{
			if(i*2+1 < 10)
				node[i].left = node[i*2+1];
			if(i*2+2 < 10)
				node[i].right = node[i*2+2];
		}
		
		postOrderRe(node[0]);
		System.out.println("***");
		postOrder(node[0]);
	}
	
	
	
	public static void postOrderRe(TreeNode biTree)
	{//后序遍历递归实现
		if(biTree == null)
			return;
		else
		{
			postOrderRe(biTree.left);
			postOrderRe(biTree.right);
			System.out.println(biTree.value);
		}
	}
	
	public static void postOrder(TreeNode biTree)
	{//后序遍历非递归实现
		int left = 1;//在辅助栈里表示左节点
		int right = 2;//在辅助栈里表示右节点
		Stack<TreeNode> stack = new Stack<TreeNode>();
		Stack<Integer> stack2 = new Stack<Integer>();//辅助栈，用来判断子节点返回父节点时处于左节点还是右节点。
		
		while(biTree != null || !stack.empty())
		{
			while(biTree != null)
			{//将节点压入栈1，并在栈2将节点标记为左节点
				stack.push(biTree);
				stack2.push(left);
				biTree = biTree.left;
			}
			
			while(!stack.empty() && stack2.peek() == right)
			{//如果是从右子节点返回父节点，则任务完成，将两个栈的栈顶弹出
				stack2.pop();
				System.out.println(stack.pop().value);
			}
			
			if(!stack.empty() && stack2.peek() == left)
			{//如果是从左子节点返回父节点，则将标记改为右子节点
				stack2.pop();
				stack2.push(right);
				biTree = stack.peek().right;
			}
				
		}
	}
}

class TreeNode//节点结构
{
	int value;
	TreeNode left;
	TreeNode right;
	
	TreeNode(int value)
	{
		this.value = value;
	}
}


4.层次遍历
    与树的前中后序遍历的DFS思想不同，层次遍历用到的是BFS思想。一般DFS用递归去实现（也可以用栈实现），BFS需要用队列去实现。
层次遍历的步骤是：
    1.对于不为空的结点，先把该结点加入到队列中
    2.从队中拿出结点，如果该结点的左右结点不为空，就分别把左右结点加入到队列中
    3.重复以上操作直到队列为空
	public static void levelOrder(TreeNode biTree)
	{//层次遍历
		if(biTree == null)
			return;
		LinkedList<TreeNode> list = new LinkedList<TreeNode>();
		list.add(biTree);
		TreeNode currentNode;
		while(!list.isEmpty())
		{
			currentNode = list.poll();
			System.out.println(currentNode.value);
			if(currentNode.left != null)
				list.add(currentNode.left);
			if(currentNode.right != null)
				list.add(currentNode.right);
		}
	}
先序遍历特点：第一个值是根节点
中序遍历特点：根节点左边都是左子树，右边都是右子树

二叉树的前序遍历、中序遍历和后序遍历之间还原二叉树
1、概念
（1）前序遍历
      a、访问根节点；b、前序遍历左子树；c、前序遍历右子树。
（2）中序遍历
      a、中序遍历左子树；b、访问根节点；c、中序遍历右子树。
（3）后序遍历
      a、后序遍历左子树；b、后续遍历右子树；c、访问根节点。
2、前序遍历和中序遍历还原二叉树
思想如下：
    a、根据前序遍历结果，第一个元素为二叉树的根结点；
    b、观察中序遍历结果，根结点左侧的为左子树，若左子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；根结点右侧的为右子树，若右子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；
    c、上面的过程是递归的。先找到当前树的根结点，然后划分为左右子树，再进入左子树重复上面的过程，最后进入右子树重复上面的过程，最终还原一棵树。
例：
    已知前序遍历：ABDHIEJKCFLMGNO
           中序遍历：HDIBJEKALFMCNGO

按照上述步骤先画出二叉树，然后在进行求解后序遍历结果。结果为：HIDJKEBLMFNOGCA
练习：
1、前序遍历：GDAFEMHZ
      中序遍历：ADEFGHMZ
    求得后序遍历结果为：AEFDHZMG
2序遍历：ADCEFGHB
      中序遍历：CDFEGHAB
    求得后序遍历结果为：CFHGEDBA
3、中序遍历和后序遍历还原二叉树
思想如下：
    a、根据后序遍历结果，最后一个元素为二叉树的根结点；
    b、观察中序遍历结果，其中根结点左侧为左子树，若左子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；其中根结点右侧为右子树，若右子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；
    c、上面的过程是递归的。先根据后序遍历结果找根结点，根结点左侧为左子树，右侧为右子树，再进入左子树重复上面的过程，最后进入右子树重复上面的过程，最终还原一棵树。
例：
    已知
中序遍历：HDIBJEKALFMCNGO
后序遍历：
HIDJKEBLMFNOGCA
         
按照上述步骤先画出二叉树，然后在进行求解前序遍历结果。结果为：
ABDHIEJKCFLMGNO
练习：可参考前序遍历和中序遍历的练习
4、前序遍历和后序遍历还原二叉树
已知前序和中序，后序和中序遍历序列之后，可以唯一确定一棵二叉树。但是，只知道前序和后序遍历序列，是无法知道哪个结点是左子树还算右子树。

树的遍历顺序大体分为三种：前序遍历（先根遍历、先序遍历），中序遍历（中根遍历），后序遍历（后根遍历）。

 

如图所示二叉树：



 

前序遍历：

前序遍历可以记为根左右，若二叉树为空，则结束返回。

前序遍历的规则：

（1）访问根节点

（2）前序遍历左子树

（3）前序遍历右子树

这里需要注意：在完成第2,3步的时候，也是要按照前序遍历二叉树的规则完成。

前序遍历的输出结果：ABDECF

中序遍历：

中序遍历可以记为左根右，也就是说在二叉树的遍历过程中，首先要遍历二叉树的左子树，接着遍历根节点，最后遍历右子树。

同样，在二叉树为空的时候，结束返回。

中序遍历的规则：

（1）中序遍历左子树

（2）访问根节点

（3）中序遍历右子树

注意：在完成第1，3步的时候，要按照中序遍历的规则来完成。

中序遍历的输出结果：DBEAFC

后序遍历：

后序遍历可以记为左右根，也就是说在二叉树的遍历过程中，首先按照后序遍历的规则遍历左子树，接着按照后序遍历的规则遍历右子树，最后访问根节点。

在二叉树为空的时候，结束返回。

后序遍历二叉树的规则：

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根节点

注意：在完成1,2步的时候，依然要按照后序遍历的规则来完成。

后序遍历的输出顺序：DEBFCA

————————————————————————————————————————————————————————————

例题：

已知前序、中序遍历，求后序遍历

前序遍历:  DBAECHMZ

中序遍历：ABCEDMHZ

先根据前序遍历得到根结点为D。根据中序遍历就可以知道ABCE为左子树，MHZ为右子树。

再根据前序遍历，D之后就是BAEC为左子树，所以B是离根节点最近的一个左子树的根结点，B为ADCE左子树的根结点，

再根据前序遍历，D之后的HMZ为右子树，      所以H是离根结点最近的一个右子树的根结点，H为HMZ右子树的根结点，

 所以：                        D

                                    ∧

                                  B   H

接下来截断为：

前序：BAEC

中序：ABCE

再根据前序遍历，左子树根结点为B，根据中序遍历就可以知道A为左子树，CE为右子树

再根据前序遍历，B之后就是A为左子树，没啥好分析了

再根据前序遍历，B之后就是EC为右子树，所以E是离根结点最近的一个右子树的根结点，E为EC右子树的根结点

所以：                    B

                              ∧

                             A  E

同理，再分析右子树，最后可得二叉树的结构为：   D

                                                                                  ∧

                                                                                B   H

                                                                              ∧     ∧

                                                                           A   E  M  Z

                                                                               ／

                                                                               C

搞定！ 一般先用前序遍历跟后序遍历分析出哪个是根结点，用中序遍历分析出左右子树！愉快的一晚！