题目一：
Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
confused what "{1,#,2,3}" means > read more on how binary tree is serialized on OJ.
分析：层次遍历的变形哈.没啥太大的变化，看代码理解下哈！
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList
> zigzagLevelOrder(TreeNode root) {
ArrayList
> result = new ArrayList
>(); if (root == null) return result; Queue
queue = new LinkedList
(); queue.add(root); int k = 1; ArrayList
list = new ArrayList
(); while (!queue.isEmpty()){ list.clear(); while (!queue.isEmpty()){ list.add(queue.remove()); } ArrayList
arrays = new ArrayList
(); for(int i=0; i
题目二：
Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
题意：给你一个array数组，让你求出这个数组所能组成的一个平衡的二叉树，很明显的递归问题哈，用分治的思想把中间的结点作为根结点，再一直递归下去就可以了哈！！
AC代码：
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedArrayToBST(int[] num) {
if (num.length == 0){
return null;
}
return buildBST(num, 0, num.length-1);
}
/*
递归调用
*/
public TreeNode buildBST(int[] num, int left, int right){
/*当left > right 的时候，表示是叶子结点的孩子了，返回null*/
if (left > right){
return null;
}
/*取中间值，作为根结点的值*/
int middle = (right + left) / 2;
TreeNode root = new TreeNode(num[middle]);
/*求出左右孩子*/
root.left = buildBST(num, left, middle-1);
root.right = buildBST(num, middle+1, right);
return root;
}
}
类似的题目：
Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
题意：跟上面的一样，只不过数组换成了链表！！果断要知道如何快速求出链表中间的那个结点哈~
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null){
return null;
}
return buildBST(head, null);
}
public TreeNode buildBST(ListNode left, ListNode right){
if (right == null && left == null){
return null;
}
if (right != null && right.next == left){
return null;
}
/*求链表中间结点的前一个结点 Begin*/
ListNode preLeft = new ListNode(0);
preLeft.next = left;
ListNode tempNode = left;
ListNode preMiddleNode = preLeft;
/*求链表中间结点的具体方法*/
while (tempNode != right && tempNode.next != right){
preMiddleNode = preMiddleNode.next;
tempNode = tempNode.next.next;
}
/*求链表中间结点的前一个结点 End*/
/*递归咯！*/
ListNode middleNode = preMiddleNode.next;
TreeNode root = new TreeNode(middleNode.val);
root.left = buildBST(left, preMiddleNode);
root.right = buildBST(preMiddleNode.next.next, right);
return root;
}
}
题目三：
Surrounded Regions(考察深度搜索)
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in tha