leetcode107.二叉树的层次遍历Ⅱ,108.将有序数组转

题目链接

二叉树的层次遍历Ⅱ

思路：queue

本题和二叉树的层序遍历一模一样，只不过需要返回其节点值自底向上的层次遍历结果。我们只需要在最后使用arrayList.add(0,val)方法即可。
代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }

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

时间复杂度分析：O(N)
额外空间复杂度：O(N)

执行结果：

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

题目链接

思路：recursion

如果输入的序列是有序的序列，我们自然而言就可以联想到二叉搜索树的中序遍历结果就是由小到大排列的。
那么，首先我们思考一个问题：重构的二叉搜索树是唯一的吗？

答案必然是否定的，因为我们可以间接认为，给定了有序的输入序列，实际上就是给定了二叉搜索树的中序遍历的结果，如果只知道中序遍历的结果是无法准确确定一个唯一的树的。如果给定了前序遍历+中序遍历的结果或者是中序遍历+后续遍历的结果则可以确定一棵唯一的二叉树，可以参考题目：leetcode105.从前序与中序遍历序列构造二叉树,106.从中序与后序遍历序列构造二叉树

所以，本题的构建方法必然不是唯一的，这里只给出了递归的求解方式，另外的代码得到的结果也可能构造出不同的树。

本题思路是通过有序的序列的中点作为构造的根节点，以根节点为中心，将数组一分为二，然后递归即可，这里面需要注意左右边界，我在这里吃了亏，提交了好几次才过..
代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums,0,nums.length - 1);
    }

    private TreeNode sortedArrayToBST(int[] nums,int left,int right){
        if(left > right){
            return null;
        }

        int rootIndex = left + ((right - left) >> 1);
        TreeNode root = new TreeNode(nums[rootIndex]);
        root.left = sortedArrayToBST(nums,left,rootIndex - 1);
        root.right = sortedArrayToBST(nums,rootIndex + 1,right);
        return root;
    }
}

时间复杂度：O(N)

额外空间复杂度：重构的二叉树是我们需要返回的结果，所以这个结果我认为是不算做额外空间的，额外空间实际上只是递归栈的深度，因为返回的树不仅仅是二叉搜索树也是一棵平衡的树，所以递归栈的深度为O(logN)

执行结果：