LeetCode. 515. Find the maximum value in each tree row___ BFS + DFS + BFS by layer

515. Find the maximum in each tree row

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

 Example 1：

 Input : root = [1,3,2,5,3,null,9]
 Output : [1,3,9]
 Example 2：

 Input : root = [1,2,3]
 Output : [1,3]
 

 Tips ：

 The range of the number of nodes in a binary tree is  [0,104]
-231 <= Node.val <= 231 - 1

Solution1( one by one BFS ):

• First, we adopt the simplest solution , That is, we are looking for the maximum value of each layer in the binary tree , Obviously, we can use wide search to traverse binary trees , Take out the elements of each layer one by one , And always maintain a maximum , At the same time, after taking out the element, put its left and right non empty child elements into the end of the queue .

Here we are one by one BFS How can I tell which layer the element is ？
We use custom classes State To achieve , You can maintain the depth of each node element .

Code1:

/** * 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; * } * } */
//  one by one BFS 
class Solution {
    
    public List<Integer> largestValues(TreeNode root) {
    
        List<Integer> res = bfs(root);
        return res;
    }

    public List<Integer> bfs(TreeNode root){
    
        Queue<State> queue = new LinkedList<State>();
        if(root == null){
    
            return new ArrayList<Integer>();
        }
        State start = new State(root,0);
        queue.offer(start);
        List<Integer> list = new ArrayList<>();
        State max_thisDepth = new State(new TreeNode(Integer.MIN_VALUE,null,null),0);
        while(queue.size()!=0){
    
            TreeNode temp = queue.peek().node;
            int now_depth = queue.peek().depth;
            if(temp.left != null){
    
                queue.offer(new State(temp.left,now_depth + 1));
            }
            if(temp.right != null){
    
                queue.offer(new State(temp.right,now_depth + 1));
            }
            State thisState = queue.poll();
            TreeNode thisNode = thisState.node;
            if(max_thisDepth.depth == thisState.depth){
    
                max_thisDepth.node.val = Math.max(max_thisDepth.node.val,thisNode.val);
            }
            else{
    
                list.add(max_thisDepth.node.val);
                max_thisDepth.node.val = thisNode.val;
                max_thisDepth.depth = thisState.depth;
            }
        } 
        list.add(max_thisDepth.node.val);
        return list;
    }
}
class State{
    
    TreeNode node;
    int depth;

    public State(TreeNode node,int depth){
    
        this.node = node;
        this.depth = depth;
    }
}

Solution2( DFS ):

• According to the situation of this question, we should use extensive search , But using deep search can also solve , We only need one Hashtable Conduct Record the maximum value of each layer that will do , In this way, when traversing a binary tree, we just need to follow At this time, traverse the depth of the node Update the hash table in real time .

Code2:

class Solution {
    
    Map<Integer,Integer> map = new HashMap<>();
    public List<Integer> largestValues(TreeNode root) {
    
        if(root == null){
    
            return new ArrayList<>();
        }
        dfs(root,0);
        List<Integer> res = new ArrayList<>();
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
    
            res.add(entry.getValue());
        }
        return res;
    }
    
    public void dfs(TreeNode root,int depth){
    
        if(map.containsKey(depth)){
    
            int value = map.get(depth);
            if(root.val > value){
    
                map.put(depth,root.val);
            }
        }
        else{
    
            map.put(depth,root.val);
        }

        if(root.left!=null){
    
            dfs(root.left,depth+1);
        }

        if(root.right!=null){
    
            dfs(root.right,depth+1);
        }

        return;
    }
}

Solution3( By layer BFS ):

• Extensive search for method one , We can optimize it , That is, there is no need to maintain a depth for each node in real time ;
• Because we only require the maximum value of each layer , We can follow One layer at a time Let's do the traversal , That is, every time we start from the queue Take out all the elements of this layer , Then it can be traversed , Because we always take out Same floor The elements of , Therefore, there is no need to consider the problem of depth , Therefore, it can be simplified ;

On the implementation side , We only need to traverse according to the length of the initial queue len, From the queue Before removal len Elements , You can get all the elements of this layer , While taking out the elements, we should not forget to put the left and right non empty elements of the taken elements into the queue , In this way, the elements in each queue are elements of the same layer , Therefore, this can have the effect of searching by layer .

Code3:

class Solution {
    

    public List<Integer> largestValues(TreeNode root) {
    
        if(root == null){
    
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        List<Integer> res = new ArrayList<>();
        
        while(!queue.isEmpty()){
    
            int this_depth_len = queue.size();
            int max = Integer.MIN_VALUE;
            while(this_depth_len != 0){
      // Take out this layer 
                TreeNode temp = queue.poll();
                max = Math.max(temp.val,max);
                if(temp.left != null)
                    queue.offer(temp.left);
                if(temp.right != null)
                    queue.offer(temp.right);   
                this_depth_len--;
            }
            res.add(max);
        }

        return res;
    }
}