LeetCode 106-110

106. 从中序与后序遍历序列构造二叉树

class Solution {
    public TreeNode helper(int[] inorder, int[] postorder, int inL, int inR, int postL, int postR) {
        if (inL > inR) {
            return null;
        }
        int rootVal = postorder[postR];
        TreeNode root = new TreeNode(rootVal);
        int index;//根结点在中序遍历中的位置
        for (index = inL; index <= inR; index++) {
            if (inorder[index] == rootVal) {
                break;
            }
        }
        int numLeft = index - inL;//左子树个数
        root.left = helper(inorder, postorder, inL, inL + numLeft - 1, postL, postL + numLeft - 1);
        root.right = helper(inorder, postorder, index + 1, inR, postL + numLeft, postR - 1);
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }
}

107. 二叉树的层次遍历 II

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode front = queue.poll();
                list.add(front.val);
                if (front.left != null) {
                    queue.offer(front.left);
                }
                if (front.right != null) {
                    queue.offer(front.right);
                }
            }
            res.add(new ArrayList<>(list));
        }
        Collections.reverse(res);
        return res;
    }
}

108. 将有序数组转换为二叉搜索树

class Solution {
    public TreeNode helper(int lo, int hi, int[] nums) {
        if (lo > hi) {
            return null;
        }
        int mid = (lo + hi) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(lo, mid - 1, nums);
        root.right = helper(mid + 1, hi, nums);
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(0, nums.length - 1, nums);
    }
}

109. 有序链表转换二叉搜索树

可以先把有序链表转换成有序数组，就变成第108题了。

class Solution {
    public TreeNode helper(int lo, int hi, List<Integer> list) {
        if (lo > hi) {
            return null;
        }
        int mid = lo + (hi - lo) / 2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = helper(lo, mid - 1, list);
        root.right = helper(mid + 1, hi, list);
        return root;
    }

    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        return helper(0, list.size() - 1, list);
    }
}

110. 平衡二叉树

class Solution {
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
}