Binary tree level traversal and examples

二叉树层序遍历

102. 二叉树的层序遍历

BFS 广度遍历：迭代.Use queues to process layer by layer

class Solution {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
    
        List<List<Integer>> re = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        if (root == null) return re;
        queue.addFirst(root);
        while (!queue.isEmpty()) {
    
            ArrayList<Integer> arraylist = new ArrayList<>();

            int n = queue.size();//This length reflects the number of each layer
            // Each of this layer is processed,Advanced teams deal first,Processing is to put values ​​and put child nodes
            for (int i = 0; i < n; i++) {
    
                root = queue.removeLast();
                arraylist.add(root.val);
                if(root.left!=null) queue.addFirst(root.left);
                if(root.right!=null) queue.addFirst(root.right);
            }
            //After finishing one layer, make it biggerlist里
            re.add(arraylist);
        }
        return re;
    }
}

DFS Depth-first traversal implements layer-order traversal 递归法

class Solution {
    
    public static List<List<Integer>> re = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
    
        re=new ArrayList<List<Integer>>(); //Likou has to write this,Otherwise static variables are not updated,默认是一个SolutionThe class is running all test points
        Order(root,0);
        return re;
    }
    public static void Order(TreeNode node,int deep){
    
        if (node==null) return;
        //Each node comes in firstdeep++ 传入的deepis the layer number of the parent node
        deep++;
        if (re.size()<deep){
    //一个size是一层,Create layers if the node is located,Create this layer first
            ArrayList<Integer> arrayList = new ArrayList<>();
            re.add(arrayList);
        }
        //Take out the layer that this node corresponds to
        List<Integer> curCheng = re.get(deep - 1);
        curCheng.add(node.val);
        Order(node.left,deep);
        Order(node.right,deep);

    }
}

107.二叉树的层次遍历II

Based on the previous topic

 List<List<Integer>> reQ= new ArrayList<>();
    for (int i=re.size();i>0;i--) {
    
                reQ.add(re.get(i-1));
     }
        return reQ;

199.二叉树的右视图

class Solution {
    
    public List<Integer> rightSideView(TreeNode root) {
    
            List<Integer> re = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        if (root == null) return re;
        queue.addFirst(root);
        while (!queue.isEmpty()) {
    
            int n = queue.size();//This length reflects the number of each layer
            // Each of this layer is processed,Advanced teams deal first,Processing is to put values ​​and put child nodes
             for (int i = 0; i < n; i++) {
    
                root = queue.removeLast();
               //判断
                if(i==n-1){
    
                    re.add(root.val);
                }
                if(root.left!=null) queue.addFirst(root.left);
                if(root.right!=null) queue.addFirst(root.right);
            }
        

        }
        return re;
    }
}

On the basis of normal layer-by-layer traversal,Determine whether it is the last of the current layer,If it's the last one, add it in.Because sometimes you see the left and sometimes you see the right,Only guaranteed to be the last of each layer.

637.二叉树的层平均值

public List<Double> averageOfLevels(TreeNode root) {
    
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    List<Double> re = new ArrayList<>();
    if (root==null) return re;
    queue.addFirst(root);
    while (!queue.isEmpty()){
    
        int size = queue.size();
        Double sum=0.0;
        for (int i=0;i<size;i++){
    
            TreeNode node = queue.removeLast();
            sum+=node.val;
            if (node.left!=null) queue.addFirst(node.left);
            if (node.right!=null) queue.addFirst(node.right);
        }
        double avg=sum/size;
        re.add(avg);
    }
    return re;
}

429.N叉树的层序遍历

class Solution {
    
    public List<List<Integer>> levelOrder(Node root) {
    
        List<List<Integer>> re = new ArrayList<>();
        if(root==null){
    
            return re;
        }
        ArrayDeque<Node> queue = new ArrayDeque<Node>();
        
        queue.add(root);
        while(!queue.isEmpty()){
    
            int n = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            for (int i =0; i<n;i++){
    
                Node node = queue.removeLast();
                list.add(node.val);
                for (Node child : node.children) {
    
                    if (child!=null){
    
                        queue.addFirst(child);
                    }
                }
            }
            re.add(list);
        }
        return  re;
    }
}

515.在每个树行中找最大值

class Solution {
    
    public List<Integer> largestValues(TreeNode root) {
    
        ArrayList<Integer> re = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        if (root==null){
    
            return  re;
        }
        queue.add(root);
        while (!queue.isEmpty()){
    
            int n = queue.size();
            int max=Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
    
                TreeNode node = queue.removeLast();
                max =Math.max(max,node.val);
                if (node.left!=null) queue.addFirst(node.left);
                if (node.right!=null) queue.addFirst(node.right);
            }
            re.add(max);
        }
       return  re;

    }
}

• 116.填充每个节点的下一个右侧节点指针

class Solution {
    
    public Node connect(Node root) {
    
        if(root==null) return null;
        ArrayDeque<Node> deque = new ArrayDeque<>();
        deque.addFirst(root);
        while (!deque.isEmpty()){
    
            int size = deque.size();
            Node per=null;
             for (int i = 0; i < size; i++) {
    
                    Node node = deque.removeLast();
                    if (node.left!=null) deque.addFirst(node.left);
                    if (node.right!=null)deque.addFirst(node.right);
                    if (per!=null){
    
                        per.next=node;
                    }
                    per=node;
                }
        }
        return root;
    }
}

• 104.二叉树的最大深度

public class 二叉树的最大深度 {
    
    public int maxDepth(TreeNode root) {
    
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        int re=0;
        if (root ==null){
    
            return re;
        }
        deque.addFirst(root);
        while (!deque.isEmpty()){
    
            int size = deque.size();
            re++;
            for (int i = 0; i < size; i++) {
    
                TreeNode node = deque.removeLast();
                if (node.left!=null) deque.addFirst(node.left);
                if (node.right!=null) deque.addFirst(node.right);

            }
        }
        return re;
    }
}

• 111.二叉树的最小深度

public class 二叉树的最小深度 {
    
    public int minDepth(TreeNode root) {
    
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        int re=0;
        if (root==null){
    
            return re;
        }
        deque.addFirst(root);
        while (!deque.isEmpty()){
    
            re++;
            int n = deque.size();
            for (int i = 0; i < n; i++) {
    
                TreeNode node = deque.removeLast();
                if (node.right!=null) deque.addFirst(node.right);
                if (node.left!=null) deque.addFirst(node.left);
                if (node.right==null&&node.left==null){
    
                   return re;
                }
            }
        }
        return re;
    }
}