Labuladong Cheat Sheet (DRAFT) by woshiamiaojiang

class Solution {

    int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        getOneSideMax(root);
        return res;
    }

    public int getOneSideMax(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = Math.max(0, getOneSideMax(root.left));
        int right = Math.max(0, getOneSideMax(root.right));
        res = Math.max(left + right + root.val, res);
        return Math.max(left, right) + root.val;
    }
}

class Solution {

    int k = 0;
    int res = 0;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        traverse(root);
        return res;
    }

    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(root.left);
        k--;
        if (k == 0) {
            res = root.val;
            return;
        }
        traverse(root.right);
    }
}

/*
    开辟一个动态数组，基底dp[0]=0。
    dp[i] = num。
    i代表目标值，num代表硬币个数。
    num初值为amt+1。代表不可能。
    每个dp[i]都与dp[i-coin]的结果相关联。
*/
class Solution {
    public int coinChange(int[] coins, int amount) {
		
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
                }
            }
        }
        return dp[dp.length - 1] == amount + 1? -1 : dp[dp.length - 1];
    }
}

class Solution {

    boolean[] used;
    List<List<Integer>> res;

    public List<List<Integer>> permute(int[] nums) {
        res = new LinkedList<>();
        used = new boolean[nums.length];
        backtrack(nums, new LinkedList<>());
        return res;
    }

    public void backtrack(int[] nums, LinkedList<Integer> track) {
				// 临时track大小满的时候
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
						// 做选择，添加，下探结果
            used[i] = true;
            track.add(nums[i]);
            backtrack(nums, track);
            used[i] = false;
            track.removeLast();
        }
    }
}

class Solution {


    HashMap<Integer, Integer> inorderValMapIdx = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderValMapIdx.put(inorder[i], i);
        }
        return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    // pre: 3 9 20 15 7
    //      T L R
    // in : 9 3 15 20 7
    //      L T R
    public TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd) {
            return null;
        }
        int rootVal = preorder[preStart];
        int inorderRootIdx = inorderValMapIdx.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(preorder, inorder, preStart + 1, preStart + inorderRootIdx - inStart, inStart, inorderRootIdx - 1);
        root.right = buildTree(preorder, inorder, preStart + inorderRootIdx - inStart + 1, preEnd, inorderRootIdx + 1, inEnd);
        return root;
    }
}