Preface

The route of brushing questions comes from Random code recording

102. Sequence traversal of binary tree

Sequence traversal

Title Description

Give you the root node of the binary tree root , Returns the Sequence traversal . （ That is, layer by layer , Access all nodes from left to right ）.

Prerequisite knowledge

Before solving this problem , We should first understand what is sequence traversal
Sequence traverses a binary tree . It is from left to right to traverse the binary tree layer by layer .
First in first out queue , According to the logic of traversal layer by layer , We can use queues to implement sequence traversal

public void levelOrderTraversal(Node root){
    
    if(root==null){
    
        return;
    }
    Queue<Node> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
    
        Node node=queue.poll();
        System.out.print(node.val+" ");
        if(node.left!=null) {
    
            queue.offer(node.left);
        }
        if(node.right!=null) {
    
            queue.offer(node.right);
        }
    }
}

Code

class Solution {
    
	public List<List<Integer>> levelOrder(TreeNode root) {
    
		if(root==null) {
    
			return new ArrayList<List<Integer>>();
		}
		
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		// Put the root node in the queue , Then continue to traverse the queue 
		queue.add(root);
		while(queue.size()>0) {
    
			// Gets the length of the current queue , This length is equivalent to   Number of nodes in the current layer 
			int size = queue.size();
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			// Take out all the elements in the queue ( That is, get the nodes of this layer ), Put it on the temporary list in 
			// If the left side of the node / The right subtree is not empty , Also put in the queue 
			for(int i=0;i<size;++i) {
    
				TreeNode t = queue.poll();
				tmp.add(t.val);
				if(t.left!=null) {
    
					queue.offer(t.left);
				}
				if(t.right!=null) {
    
					queue.offer(t.right);
				}
			}
			// Will be temporary list Add to the final returned result 
			res.add(tmp);
		}
		return res;
	}
}

107 Sequence traversal of binary tree II

107. Sequence traversal of binary tree II

Title Description

Give you the root node of the binary tree root , Returns its node value Bottom up sequence traversal . （ That is, from the layer where the leaf node is to the layer where the root node is , Traversal layer by layer from left to right ）

Tips ：

The number of nodes in the tree is in the range [0, 2000] Inside
-1000 <= Node.val <= 1000

In fact, the idea of this question is the same as that of the above question , Just reverse the elements in the set at last

Code

class Solution {
    
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    
        List<List<Integer>> list=new ArrayList();
         List<List<Integer>> rs=new ArrayList();
        if(root==null){
    
            return rs;
        }
        Queue<TreeNode> queue=new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
    
            // Get how many elements there are in the current layer 
            int len=queue.size();
            List<Integer> temp=new ArrayList();
            for(int i=0;i<len;i++){
    
                TreeNode node= queue.poll();
                temp.add(node.val);
                if(node.left!=null){
    
                    queue.offer(node.left);
                }
                if(node.right!=null){
    
                    queue.offer(node.right);
                }
            }
              list.add(temp);
        }
      
        // reverse 
      for(int i=list.size()-1;i>=0;i--){
    
          rs.add(list.get(i));
      }
        return rs;

    }
}

199. Right side view of binary tree

199. Right side view of binary tree

Title Description

Given a binary tree The root node root, Imagine yourself on the right side of it , In order from top to bottom , Returns the value of the node as seen from the right .

Ideas

When the sequence traverses , Determine whether to traverse to the last element of the layer , If it is , Just put it in list Collection , Then return list That's all right. .

Code

class Solution {
    
    public List<Integer> rightSideView(TreeNode root) {
    
        List<Integer> list=new ArrayList();
        Queue<TreeNode> queue=new LinkedList();
        if(root==null) return list;
        queue.offer(root);
        /**  We need to determine whether to traverse the last node of the current hierarchy  */
            while(!queue.isEmpty()){
    
                int len=queue.size();
                for(int i=0;i<len;i++){
    
                    TreeNode node=queue.poll();
                    if(node.left!=null){
    
                        queue.offer(node.left);
                    }
                    if(node.right!=null){
    
                        queue.offer(node.right);
                    }
                    // Determine whether to traverse to the last node 
                    if(i==len-1){
    
                        list.add(node.val);
                    }
                }
            }
        return list;
        }
    
}

637. The layer average of a binary tree

637. The layer average of a binary tree

Title Description

Given the root node of a non empty binary tree root , Return the average value of nodes in each layer in the form of array . Differ from the actual answer 10-5 Answers within are acceptable .

Tips ：

The number of nodes in the tree is [1, 104] Within the scope of
-231 <= Node.val <= 231 - 1

Ideas

We only need to traverse the sequence , Get how many elements there are in the current layer , Then add their element values , Then add the average to list Collection

Code

class Solution {
    
    public List<Double> averageOfLevels(TreeNode root) {
    
        List<Double> list=new ArrayList();
        Queue<TreeNode> queue= new LinkedList();
        if(root==null){
    
            return list;
        }
        queue.offer(root);
       double sum=0.0;
        while(!queue.isEmpty()){
    
            // Get how many elements there are in this layer 
            int len=queue.size();
            for(int i=0;i<len;i++){
    
                TreeNode node=queue.poll();
                sum+=node.val;
                if(node.left!=null){
    
                    queue.offer(node.left);
                }
                if(node.right!=null){
    
                    queue.offer(node.right);
                }
            }
            list.add( sum/len);
            sum=0;
        }
        return list;

    }
}

429.N Sequence traversal of the fork tree

Title Description

Given a N Fork tree , Returns the sequence traversal of its node value .（ From left to right , Layer by layer traversal ）.

The serialization input of the tree is traversed by sequence , Each group of sub nodes is composed of null Value separation （ See example ）.

Tips ：

The height of the tree will not exceed 1000
The total number of nodes in the tree is [0, 10^4] Between

Ideas

This problem is actually the same as the sequence traversal of binary tree , The difference is just that , about N Fork tree , A node may have multiple child nodes

Code

class Solution {
    
      public List<List<Integer>> levelOrder(Node root) {
    
        if (root == null) {
    
            return new ArrayList<List<Integer>>();
        }

        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Queue<Node> queue = new ArrayDeque<Node>();
        queue.offer(root);

        while (!queue.isEmpty()) {
    
            int cnt = queue.size();
            List<Integer> level = new ArrayList<Integer>();
            for (int i = 0; i < cnt; ++i) {
    
                Node cur = queue.poll();
                level.add(cur.val);
                for (Node child : cur.children) {
    
                    queue.offer(child);
                }
            }
            ans.add(level);
        }

        return ans;
    }
}

515. Find the maximum in each tree row

515. Find the maximum in each tree row

Title Description

Given the root node of a binary tree root , Please find the maximum value of each layer in the binary tree .

Ideas

Sequence traversal , Use a variable temp To record the maximum value of the node that the layer has traversed ,temp And the current node val Compare , Assign the larger value of the two to temp

Code

class Solution {
    
    public List<Integer> largestValues(TreeNode root) {
    
        if(root==null){
    
            return new ArrayList<Integer>();
        }
        List<Integer> list = new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
    
            int len=queue.size();
            int temp=Integer.MIN_VALUE;
            for(int i=0;i<len;i++){
    
                TreeNode node= queue.poll();
                temp=Math.max(temp,node.val);
                if(node.left!=null){
    
                    queue.offer(node.left);
                }
                if(node.right!=null){
    
                    queue.offer(node.right);
                }
            }
            list.add(temp);
        }
            return list;

    }
}

116. Fill in the next right node pointer for each node

116. Fill in the next right node pointer for each node

Title Description

Ideas

During sequence traversal , We need to judge , Is the node we traverse the last element of this layer , If it's not the last element , Then let the current node next Point to next node

Code

class Solution {
    
    public Node connect(Node root) {
    
        if(root==null) return null;
        
        Queue<Node> queue=new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
    
            int len=queue.size();
            for(int i=0;i<len;i++){
    
                Node curr= queue.poll();
                // Judge whether there are nodes on the same layer 
                // If there are nodes , be next Point to next node , Otherwise, it points to empty 
                if(i!=len-1){
    
                    // Note that there is another node , At this point, we call element Method to get the first element , At this time, the team leader element is the next node of the current node 
                    curr.next=queue.element();
                }
                // Add the left and right children of the current node to the queue 
                if(curr.left!=null){
    
                    queue.offer(curr.left);
                }   
                if(curr.right!=null){
    
                    queue.offer(curr.right);
                }             
            }
        }
        return root;
    }
}

104. The maximum depth of a binary tree

104. The maximum depth of a binary tree

Title Description

Ideas

Using iterative method , Sequence traversal is the most appropriate , Because the maximum depth is the number of layers of the binary tree , It is very consistent with the way of sequence traversal .

In a binary tree , Layer by layer to traverse the binary tree , Record the number of layers traversed, which is the depth of the binary tree

Code

// Non recursive 
class Solution {
    
    public int maxDepth(TreeNode root) {
    
        if(root==null) return 0;
        int depth=0;
        Queue<TreeNode> queue=new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
    
            int len=queue.size();
            // As long as all nodes on the current layer are queued , be depth+1
            for(int i=0;i<len;i++){
    
                TreeNode node=queue.poll();
                if(node.left!=null){
    
                    queue.offer(node.left);
                }
                if(node.right!=null){
    
                    queue.offer(node.right);
                }
            }
            depth++;


        }
        return depth;
    }
}

Other people's solutions

ACM Player Illustration LeetCode The maximum depth of a binary tree （ recursive + Non recursive ）| Programming Wenqing Li dog egg

111. Minimum depth of binary tree

111. Minimum depth of binary tree

Title Description

Given a binary tree , Find out the minimum depth .

The minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node .

explain ： A leaf node is a node that has no children .

Ideas

Use the sequence traversal method to traverse the whole tree .
When we find a leaf node , Directly return the depth of this leaf node . The nature of breadth first search ensures that the depth of the first leaf node to be searched must be the smallest .

Code

class Solution {
    
    public int minDepth(TreeNode root) {
    
         if (root == null) {
    
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
    
            int size = queue.size();
            depth++;
            TreeNode cur = null;
            for (int i = 0; i < size; i++) {
    
                cur = queue.poll();
                // If the left and right children of the current node are empty , Returns the minimum depth directly 
                if (cur.left == null && cur.right == null){
    
                    return depth;
                }
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return depth;
    }
}

Other people's solutions

ACM Player Illustration LeetCode Minimum depth of binary tree （ recursive + Non recursive ）| Programming Wenqing Li dog egg