題目：105. Construct Binary Tree from Preorder and Inorder Traversal

連結：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

• 等級：Medium

class Solution {
    private int i = 0;//inorder
    private int p = 0;//preorder
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MIN_VALUE);
    }
    private TreeNode build(int[] preorder, int[] inorder, int stop) {
        if (p >= preorder.length)
            return null;
        //剛好為parent時跳過換右樹
        if (inorder[i] == stop) {
            ++i;
            return null;
        }

        TreeNode node = new TreeNode(preorder[p++]);
        node.left = build(preorder, inorder, node.val);
        node.right = build(preorder, inorder, stop);
        return node;
    }
}

• Time complexity: O(n)
• Space complexity: O(n)

題目：1161. Maximum Level Sum of a Binary Tree

連結：https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/

• 等級：Medium

解題思路

1. 加總每個level的值，比對大小

class Solution {
    int levelVal[] = new int[150];

    public int maxLevelSum(TreeNode root) {
        for (int i = 0; i < 150; ++i) {
            levelVal[i] = Integer.MIN_VALUE;
        }
        find(root, 1);
        int max = 1;
        for (int i = 1; i < 150; ++i) {
            if (levelVal[max] < levelVal[i]) max = i;
        }
        return max;
    }

    public void find(TreeNode root, int level) {
        if (root == null) return;
        if (levelVal[level] != Integer.MIN_VALUE) levelVal[level] += root.val; else levelVal[level] = root.val;
        find(root.left, level + 1);
        find(root.right, level + 1);
    }
}

• Time complexity: O(n)
• Space complexity: O(n)