[数据结构与算法]二叉树的层序遍历(BFS)

二叉树的层序遍历（bfs）

思想：

二叉树的层序遍历主要是运用bfs的思想，进行一层一层的遍历

BFS:

创建队列Queue,然后从当前一层的节点进行取值操作，然后遍历下一层的节点，如此反复进行

102.二叉树层序遍历

题目

思路

class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        //设置优先队列
        Queue<TreeNode> queue = new ArrayDeque<>();
        //层序遍历
        if (root != null) {
            queue.add(root);
        }
        
        //开始进行层序遍历
        //层序遍历临界条件是：队列不为空，也就是没有遍历完成
        while (!queue.isEmpty()){
            //获取当前队列的长度
            int n = queue.size();  
            List<Integer> num = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                //先从队列里面取出来这些值
                TreeNode poll = queue.poll();
                //加入num，然后进行左右字数的遍历
                num.add(poll.val);
                if (poll.left!=null){
                    //将左右子树加入优先队列
                    queue.add(poll.left);
                }
                if (poll.right!=null){
                    //将左右子树加入优先队列
                    queue.add(poll.right);
                }
                
            }
            res.add(num);
        }
        return res;
    }
}

103.二叉树的锯齿形层序遍历

题目

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func zigzagLevelOrder(root *TreeNode) [][]int {
	res := [][]int{}
	//优先队列
     queue := list.New()
	//将root进行Push进去的操作
	if root!=nil {
		queue.PushBack(root)
	}
	//临界值是什么，如果进行层序遍历
	//临界条件是队列不能为空，因为我们需要不断进行入队，出队的操作
    //这个是变种，要求不仅queue.Len()>0,而且需要记录每层的值
	for level:=0;queue.Len()>0;level++ {
		length := queue.Len()
		result := []int{}
		//每次push都需要添加val的值
		//后面还需要跟一个*TreeNode的类型

     
		for i := 0; i < length; i++ {
			node := queue.Remove(queue.Front()).(*TreeNode)

			if node.Left != nil {
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
			}
			result = append(result,node.Val)
            
		}
        if(level%2==1){
            for i, n := 0, len(result); i < n/2; i++ {
                result[i], result[n-1-i] = result[n-1-i], result[i]
            }
        }
		//添加到一维数组之后需要添加到二维数组
       res = append(res,result)
	}
	return res
}

199.二叉树的右视图

题目：

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public static List<Integer> rightSideView(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        //创建一个优先队列
        Queue<TreeNode> queue = new ArrayDeque<>();
        //首先判断root是否为null
        //不为null就把root取出来
        if(root != null) {
            queue.add(root);
        }
        while(!queue.isEmpty()){
            List<Integer> result = new ArrayList<>();
            //需要先判断n
            int n = queue.size();
            for(int i = 0; i < n ; i++){
                //取出来当前层的结点
                TreeNode node = queue.poll();
                result.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            res.add(result);
            //开始层序遍历
        }
        List<Integer> num = new ArrayList<>();
        for (int i = 0; i <res.size() ; i++) {
            num.add(res.get(i).get(res.get(i).size()-1));
        }

        return num;
    }
}