Analysis and java implementation of search related topics in binary tree in Leetcode

Analysis and java implementation of search related topics in binary tree in Leetcode

In fact, there are some miscellaneous problems in this category. It is basically to find some or a specific value in the binary tree. There are many problems. We will summarize them through two or three articles, but generally speaking, it is basically BFS, which can be solved by divide and conquer.

Let's start with simplicity!

  • [513] Find Bottom Left Tree Value
  • [199] Binary Tree Right Side View
  • [515] Find Largest Value in Each Tree Row
  • [671] Second Minimum Node In a Binary Tree
  • [116] Populating Next Right Pointers in Each Node
  • [117] Populating Next Right Pointers in Each Node II
  • [623] Add One Row to Tree
  • [637] Average of Levels in Binary Tree
  • [404] Sum of Left Leaves

Find Bottom left Tree value

In fact, these two problems are to find the value of the leftmost node at the bottom of the binary tree. When we encounter the problem of hierarchical traversal, our first consideration is BFS. In the process of BFS, we constantly update the value of the leftmost node in each row, and then when BFS exits, this value is the result we need to return.

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if(root == null)return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode node = queue.poll();
                if(i == 0)res = node.val;
                if(node.left != null)queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return res;
    }
}

Binary Tree Right Side View

Much like the previous question, it is actually to find the value of the last edge node of each layer in the binary tree, record it, and then return it as an array. The same can be solved by BFS

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> results = new ArrayList<>();
    	if (root == null) return results;
    	Queue<TreeNode> queue = new LinkedList<>();
    	queue.offer(root);
    	while (!queue.isEmpty()) {
        	int size = queue.size();
        	for (int i = 0; i < size; i++) {
            	TreeNode node = queue.poll();
            	if (i == size - 1) results.add(node.val);
            	if (node.left != null) queue.offer(node.left);
            	if (node.right != null) queue.offer(node.right);
        	}
    	}
    	return results;
    }
}

Find Largest Value in Each Tree Row

It also needs sequence traversal. In the process of BFS, use a variable to record the maximum value, and store the maximum value in the return array at the end of each layer.

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

Second Minimum Node In a Binary Tree

Finding the second smallest number in the binary tree is a little special. Each node either has no child nodes, or there must be two child nodes, and the value of the current node will not be greater than that of the child nodes. Based on this characteristic, the root node must be the first small value, and then we constantly traverse the sub array, and then maintain a value. If it is larger than the root node and smaller than the current value, we will update the current value.

class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        int first = root.val;
        long second = Long.MAX_VALUE;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val != first && node.val < second) second = node.val;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return (second == first || second == Long.MAX_VALUE) ? -1 : (int)second;
    }
}

Populating Next Right Pointers in Each Node

Connect the right sibling node of each node of the perfect binary tree.
This problem is a little special. There are not only left and right subtrees in the node of the binary tree, but also a next pointer to the sibling node at the same level on the right.
We use the recursive divide and conquer method to solve this problem. First, check whether the current node has a left child node. If so, point the next of the current left child node to the right, and it doesn't matter if the right child node is null. If the current next is not empty, it means that the current node has siblings, and the next of the current right child node should also point to the left child node of the sibling node.

class Solution{
	public Node connect(Node root){
		if(root == null) return;
		if(root.left != null){
			root.left.next = root.right;
		}
		if(root.right != null){
			root.right.next = (root.next == null)?null:root.next.left;
		}
		connect(root.left);
		connect(root.right);
		return root;
	}
}

Populating Next Right Pointers in Each Node II

Compared with the previous question, there is no perfect binary tree in this question. There is a case where a node has only left or right children. In this case, the divide and conquer method will cause problems, because the left child node cannot be connected to the left child node of the current sibling node. At this time, the BFS of sequence traversal is used to deal with this problem, so that the next of each node, It must be the next node in the queue.

class Solution {
    public Node connect(Node root) {
        if(root == null){
            return null;
        }
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                Node node = queue.poll();
                if(i < size-1){
                //The last node is not processed
                    node.next = q.peek();
                }
                if(node.left != null) q.offer(node.left);
                if(node.right != null)q.offer(node.right);
            }
            
        }
        return root;
    }
}

Add One Row to Tree

This problem is also a derivation of level traversal. Enter a root node, a depth and an integer value, and let us insert a new node with a line of integer value at the corresponding depth. Similarly, we use BFS plus the detection of the number of layers. When it does not arrive, it will be normal BFS. When it reaches the level we need, we can insert two new nodes into all nodes in the queue.

/**
 * 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 TreeNode addOneRow(TreeNode root, int v, int d) {
        if(root == null)return null;
        if(d == 1){
            TreeNode newRoot = new TreeNode(v);
            newRoot.left = root;
            return newRoot;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            if(d-- == 0)return root;
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                if(d == 1){
                    TreeNode left = new TreeNode(v);
                    left.left = node.left;
                    node.left = left;
                    TreeNode right = new TreeNode(v);
                    right.right = node.right;
                    node.right = right;
                }else{
                    if(node.left != null)queue.offer(node.left);
                    if(node.right != null)queue.offer(node.right);
                }
            }
        }
        return root;
    }
}

Average of Levels in Binary Tree

As the name suggests, it is to calculate the average value of each layer, which can be easily solved with BFS

List<Double> results = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        long sum = 0;
        int count = 0;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            sum += node.val;
            count++;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        results.add((double) sum / count);
    }
    return results;

Sum of Left Leaves

Statistics of the sum of all left leaf nodes can be processed with BFS. When a left child node appears in each layer, it will be added to the return value.

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null || root.left == null && root.right == null)return 0;
        int sum = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left != null && node.left.left == null && node.left.right == null) sum+= node.left.val;
            if(node.left != null) queue.offer(node.left);
            if(node.right != null)queue.offer(node.right);
        }
        return sum;
    }
}

Today's problems are basically search and statistical problems that can be solved by BFS, which is still very simple.

Tags: Java Algorithm leetcode queue Binary tree bfs

Posted by HavokDelta6 on Mon, 23 May 2022 10:13:08 +0300