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

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

/**
 * 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 TreeNode sortedArrayToBST(int[] nums) {
        int n=nums.length;
        return s(0,n,nums);
    }
    public TreeNode s(int begin,int end,int[] nums) {
        if(begin>=end)
            return null;
        int mid=(begin+end)/2;
        return new TreeNode(nums[mid],s(begin,mid,nums),s(mid+1,end,nums));
    }
}

个人总结： 思路清晰。

105. 从前序与中序遍历序列构造二叉树

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

/**
 * 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 TreeNode buildTree(int[] preorder, int[] inorder) {
        return b(preorder,inorder,0,inorder.length);
    }
    int begin1=0;
    public TreeNode b(int[] preorder,int[] inorder,int begin2,int end2) {
        if(begin2>=end2)
            return null;
        for(int i=begin2;i<end2;i++)
        {
            if(inorder[i]==preorder[begin1])
            {
                begin1++;
                return new TreeNode(preorder[begin1-1],b(preorder,inorder,begin2,i),b(preorder,inorder,i+1,end2));
            }
                
        }
        return null;
    }
}

个人总结： 对相关知识较为了解。

103. 二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7

返回锯齿形层序遍历如下：

[
[3],
[20,9],
[15,7]
]

/**
 * 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Deque<TreeNode> tree=new LinkedList<TreeNode>();
        List<List<Integer>> a=new ArrayList<List<Integer>>();
        if(root!=null)
            tree.push(root);
        int c=tree.size(),x=0;
        while(!tree.isEmpty())
        {   
            List<Integer> b=new ArrayList<Integer>();
            while(c>0)
            {
                if(x%2==0)
                {
                    if(tree.peekLast().left!=null)
                        tree.addFirst(tree.peekLast().left);
                    if(tree.peekLast().right!=null)
                        tree.addFirst(tree.peekLast().right);
                    b.add(tree.peekLast().val);
                    tree.removeLast();    
                }
                else
                {
                    if(tree.peekFirst().right!=null)
                        tree.addLast(tree.peekFirst().right);
                    if(tree.peekFirst().left!=null)
                        tree.addLast(tree.peekFirst().left);
                    
                    b.add(tree.peekFirst().val);
                    tree.removeFirst();        
                }
                c--;
            }
            x++;
            c=tree.size();
            a.add(b);
        }
        return a;
    }
}

个人总结： 总体没什么问题，有一些小bug，一开始还没发现。