前序遍历
image.png
访问顺序
- 根节点，前序遍历左子树，前序遍历右子树（遍历子树的时候，就是递归思路）
- 7（根节点）
- 4，2，1，3，5（左子树）
- 9，8，11，10，12（右子树）
/**
* 前序遍历 144
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {//144 前序
List<Integer> retList = new ArrayList<>();
preorderTraversal(retList,root);
return retList;
}
private void preorderTraversal(List<Integer> retList, TreeNode root){
if (root != null) {
retList.add(root.val);
preorderTraversal(retList,root.left);
preorderTraversal(retList,root.right);
}
}
中序遍历
image.png
访问顺序
- 中序遍历左子树，根节点，中序遍历右子树
- 1，2，3，4，5，6（左子树）
- 7（根节点）
- 8，9，10，11，12（右子树）
/**
* 中序遍历 94
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> retList = new ArrayList<>();
inorderTraversal(retList, root);
return retList;
}
private void inorderTraversal(List<Integer> retList, TreeNode root) {
if (root != null) {
inorderTraversal(retList, root.left);
retList.add(root.val);
inorderTraversal(retList, root.right);
}
}
后序遍历
image.png
访问顺序
- 后序遍历左子树，后序遍历右子树，最后是根节点，
- 1，3，2，5，4（左子树）
- 8，10，12，11，9（右子树）
- 7（根节点）
/**
* 后序遍历 145
* @param root
* @return
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> retList = new ArrayList<>();
postorderTraversal(retList, root);
return retList;
}
private void postorderTraversal(List<Integer> retList, TreeNode root) {
if (root != null) {
postorderTraversal(retList, root.left);
postorderTraversal(retList, root.right);
retList.add(root.val);
}
}
层序遍历（队列方案，FIFO先进先出）
image.png
按照二叉树的层序遍历即可
- 采用队列思想的大致思路：按照上图推导，根节点 7先入队
- 进行循环操作，根节点7出队。
- 左子节点4入队， 右子节点9入队。
- 左右子节点加入完毕后，进入下一个循环，4出队，4的左右子节点2，5入队 （此时队列9，2，5）
- 继续循环 9出队，9的子左右节点8，11入队，（此时队列 2，5，8，11，也就是树第三层）
- 一层层循环，直到消息队列为空结束遍历。
/**
* 层序遍历 102
* @param root
* @return
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> retList = new ArrayList<>();
if (root == null) return retList;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> valList = new ArrayList<>();
Queue<TreeNode> tmpQueue = new LinkedList<>();
while (!queue.isEmpty()) {
TreeNode tmpNode = queue.poll();
valList.add(tmpNode.val);
if (tmpNode.left != null) {
tmpQueue.offer(tmpNode.left);
}
if (tmpNode.right != null) {
tmpQueue.offer(tmpNode.right);
}
}
retList.add(valList);
queue = tmpQueue;
}
return retList;
}
