大家好，又见面了，我是你们的朋友全栈君。

首先我们有这么一颗二叉树：

public class TreeNode { 
   
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() { 
   
    }

    TreeNode(int val) { 
   
        this.val = val;
    }
}

• 前序遍历：根结点 —> 左子树 —> 右子树（先遍历根节点，然后左右）

这棵树的前序遍历为：ABDEGHCF

代码实现:

public List<Integer> preorderTraversal(TreeNode root) { 
   
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) { 
   
        if (root == null) { 
   
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }

• 中序遍历：左子树—> 根结点 —> 右子树（在中间遍历根节点）

这棵树的中序遍历为：DBGEHACF

代码实现:

public List<Integer> inorderTraversal(TreeNode root) { 
   
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

public void inorder(TreeNode root, List<Integer> res) { 
   
        if (root == null) { 
   
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }

• 后序遍历：左子树 —> 右子树 —> 根结点（最后遍历根节点）

这棵树的后序遍历为：DGHEBFCA

代码实现:

public List<Integer> postorderTraversal(TreeNode root) { 
   
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

public void postorder(TreeNode root, List<Integer> res) { 
   
        if (root == null) { 
   
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }

• 层次遍历：按层次遍历

这棵树的层次遍历为：ABCDEFGH

代码实现

public List<List<Integer>> levelOrder(TreeNode root) { 
   
		if(root == null) { 
   
			return new ArrayList<List<Integer>>();
		}
		
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		//将根节点放入队列中，然后不断遍历队列
		queue.add(root);
		while(queue.size()>0) { 
   
			//获取当前队列的长度，这个长度相当于 当前这一层的节点个数
			int size = queue.size();
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			//将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
			//如果节点的左/右子树不为空，也放入队列中
			for(int i=0;i<size;++i) { 
   
				TreeNode t = queue.remove();
				tmp.add(t.val);
				if(t.left!=null) { 
   
					queue.add(t.left);
				}
				if(t.right!=null) { 
   
					queue.add(t.right);
				}
			}
			//将临时list加入最终返回结果中
			res.add(tmp);
		}
		return res;
	}

ps: 所谓的前序、中序、后续，就是对根节点而言的，左右的遍历顺序不变，前序就是根节点最先遍历，然后左右；中序就是把根节点放在中间遍历；后序则是把根节点放在最后遍历。

• 笔试题：已知二叉树前序遍历为：ABDEGHCF，中序遍历为：DBGEHACF，求后序遍历

分析：

1. 首先我们由前序遍历可知根节点为A
2. 已知根节点为A，由中序遍历可知左子树为DBGEH,右子树为CF

确定这两点后就很容易推算出原来的二叉树的样子了。
我们看到右子树节点为CF，中序遍历也是CF，那么就可以推断出现在的二叉树右边是这个样子：

为什么F不是左子树呢，因为如果F在左边，中序遍历的顺序就变成FC了

由前序遍历AB可以知，A的左子树肯定是B，那么现在的树就是这样的：

再由中序遍历DB可知，D为B的左子树

现在只剩下EGH没确定了
首先我们要确定的是D肯定没有子树，如果有，中序遍历就不会是DB了
由前序遍历可知E节点只能是B的右子树了

，最后由中序遍历GEH可知完整的二叉树为：

推断出整棵树后其他的遍历就都很容易写出来了。

这种题的关键是确定根节点和左右子树。如果是已知后序遍历，也是一样的最后一个就是根节点。

关于我

​ 觉得文章不错请扫码关注我吧

​