LeetCode85+105+114+124

Ideas

Iterate through the array one row at a time , Then calculate the height of the current row and its upper row height Array , Then the maximum area of the rectangle becomes 84 The same type of questions , Direct application 84 The code of the question can be .

Code

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int [] height = new int[matrix[0].length];
        int index = 0;
        int res = 0;
        for(int i = 0;i <matrix.length;i++ ){
            for(int j =0;j<matrix[i].length;j++){
                if(matrix[i][j] == '0'){
                    height[j] = 0;
                }else{
                    height[j] +=1;
                }
            }
            res = Math.max(res,largestRectangleArea(height));
        }
        return res;
    }

    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for(int i = 0;i<=heights.length;i++){
            int h =0;
            if(i == heights.length){
                h = 0;
            }else{
                h = heights[i];
            }
            while(!stack.isEmpty() && h<heights[stack.peek()]){
                int height = heights[stack.pop()];
                int start = (stack.isEmpty()) ? -1:stack.peek();
                int area = (i-start-1)*height;
                res = Math.max(res,area);
            }
            stack.push(i);
        }
        return res; 
    }
}

105. Construction of binary trees from traversal sequences of preorder and middle order

Ideas

         The first node traversed from the preorder is the root node of the binary tree , And the left side of the vertex traversed by the preceding sequence , Is the middle order traversal to the left of the vertex , The point at which the distance of the length traversed by the left middle order is taken from the vertex , Is the set of preordered traversals on the left of the vertex .

        The same is true on the right . Therefore, it is easier to implement the above idea by using recursion .

Code

/**
 * 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 {
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 1){
            return new TreeNode(preorder[0]);
        }
        for(int i =0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        TreeNode res = fun(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
        return res;
    }

    public TreeNode fun(int[] preorder, int[] inorder,int pl,int pr,int il,int ir){
        if(pl > pr || il > ir){
            return null;
        }
        int k = map.get(preorder[pl]) - il; // map.get(pre[pl]) Is the position of the root node in the middle order traversal ,k Is the length of the pre - and middle order traversal of the subtree 
        TreeNode root = new TreeNode(preorder[pl]);
        root.left = fun(preorder,inorder,pl+1,pl+k,il,il+k-1);  // Left subtree preorder traversal , Left subtree middle order traversal 
        root.right = fun(preorder,inorder,pl+k+1,pr,il+k+1,ir); // Right subtree preorder traversal , Order traversal in right subtree 
        return root;
    }
}

114. The binary tree is expanded into a list

Ideas

The first is to start from the root node , Stack all nodes in turn . Then pop up the top element of the stack and write cur, After pop-up, put the right child and the left child of the top element on the stack in turn , Then judge whether the current stack is empty , If it is not empty, the cur The right child of is designated as the current node , The left child is left blank .

Code

/**
 * 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 void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(cur.right != null) stack.push(cur.right);
            if(cur.left != null) stack.push(cur.left);
            if(!stack.isEmpty()){
                cur.right = stack.peek();
            }
            cur.left = null;
        }

    }
}
    

124. The maximum path in a binary tree and

Ideas

Use recursion to solve this problem . The recursive function is defined as that the result returned each time is the maximum value of the leftmost or rightmost subtree of the node + The value of this node . Then in the recursive function , use res To save the final results .

Code

/**
 * 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 {
    int res = -10000;
    public int maxPathSum(TreeNode root) {
        if(root == null){
            return 0;
        }
        fun(root);
        return res;
    }
    public int fun(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = Math.max(0,fun(root.left));
        int right = Math.max(0,fun(root.right));
        res = Math.max(res,(root.val+left+right));
        return Math.max(left,right)+root.val;
    }
}