LeetCode85+105+114+124

思路

每次遍历数组的一行，然后计算当前行及其以上行的高度为height数组，然后求的矩形最大面积就变为84题一样的类型了，直接套用84题的代码即可。

代码

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. 从前序与中序遍历序列构造二叉树

思路

        从前序遍历的第一个节点就是该二叉树的根节点，而前序遍历的顶点的左边，就是该顶点的左边的中序遍历，从顶点取左边中序遍历的长度的距离的点，就是顶点左边的前序遍历的集合。

        右边也是同理。所以选用递归就比较容易实现上面的思路。

代码

/**
 * 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])是中序遍历中根节点位置，k是子树前序和中序遍历的长度
        TreeNode root = new TreeNode(preorder[pl]);
        root.left = fun(preorder,inorder,pl+1,pl+k,il,il+k-1);  //左子树前序遍历，左子树中序遍历
        root.right = fun(preorder,inorder,pl+k+1,pr,il+k+1,ir); //右子树前序遍历，右子树中序遍历
        return root;
    }
}

114. 二叉树展开为链表

思路

首先就是从根节点开始，将所有节点依次入栈。然后将栈顶元素弹出记做cur，弹出后将栈顶元素的右孩子和左孩子依次入栈，接着判断下当前栈是否为空，如果不为空就将cur的右孩子指定为当前节点，其左孩子置为空。

代码

/**
 * 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. 二叉树中的最大路径和

思路

运用递归的方法来解决这个问题。递归函数定义为每次返回的结果是该节点最左或者最右子树的最大值+该节点的值。然后在递归函数中，用res来保存最后的结果。

代码

/**
 * 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;
    }
}