二叉树（前序、中序、后序遍历图片步骤详解）

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

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

代码语言：javascript复制

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

    TreeNode() { 
   
    }

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

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

这棵树的前序遍历为：ABDEGHCF

代码实现:

代码语言：javascript复制

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

代码实现:

代码语言：javascript复制

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

代码实现:

代码语言：javascript复制

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

代码实现

代码语言：javascript复制

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