二叉树遍历汇总

二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//BFS:广度优先搜索
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();//用队列来操作
		if(root==null) {
			return new ArrayList<>();//因为返回值类型是List
		}
		//第一层：根节点入队列
		queue.add(root);

		List<List<Integer>> res = new ArrayList<>();//存放所有层数据

		while(!queue.isEmpty()){
			int level = queue.size();//这一层的结点数，用于判断该层是否循环结束
			List<Integer> list = new ArrayList<>();//用于存放当前层数据

			for(int i=0;i<level;i++){//遍历这一层
				TreeNode cur = queue.poll();//出队列，并作为父结点，也是当前层数据
				list.add(cur.val);//将当前层数据放进去
				//下一层的数据入队列，作为下一层循环新的父结点
				if(cur.left!=null){
					queue.add(cur.left);//如果左孩子不为空，就放入队列中
				}
				if(cur.right!=null){
					queue.add(cur.right);
				}
			}
			res.add(list);//当前层结束后，将当前层放入List，重新开始for循环
		}
		return res;
    }
}

总结：
1.用LinkedList来构建队列queue，用于辅助操作，每次入队一层，先将根结点入队；
2.构建ArrayList存放所有层的数据；
3.构建ArrayList存放一层的数据；
4.将队列中的队首出队，作为父结点

1.先将1入队，再出队列，放入list；【1】
2.将1的左右孩子入队，for循环结束，将当前层list入所有层的res中；【2 3】
3.计算到level=2，开始新的for循环，将先入队的的2出队，放入list，并作为父结点，将2的左右孩子入队；【3 4 5】
4.将3出队，并放入list，并作为父结点，将3的左右孩子入队，当前层for循环结束；【4 5 6】
5.level=3，将4出队，放入list，将4的孩子7入队；【5 6 7】
6.将5出队，判断没有孩子结点，继续循环，6,7也出队，进入list中

二叉树的中序遍历

给定一个二叉树，返回它的中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while(curr != null || !stack.isEmpty()){
            //将左子树逐个入栈
            if(curr != null){
                stack.push(curr);
                curr = curr.left;
            }else{//即到达了树的最底层之下，curr=null
                curr = stack.pop();//栈顶的即为中序遍历第一个节点
                //stack.pop();//因为pop()没有返回值
                list.add(curr.val);//节点数值直接入队列
                curr = curr.right;//若还未到达父结点，则curr.right=null，继续入队列
            }
        }
        return list;
    }
}