題目一：
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 that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
分析：給你一個數組，裡面包含了x(或者X) 還有 o(或者O)，要求我們把o(或者O)被x(或X)包圍的情況，轉換成 o -> x 而 O -> X
這個題目，其實是典型的廣度搜索吧。。
解題方法：居然所有的邊界o(或者O),我們都認為它是不被包圍的，那麼我們只要從邊界入手就可以了...我們用一個二維數組flags來確定每個位置該出現什麼字母，如：flags[row][col] = 0 則 row行 col列出現的字母為x(或者X), flags[row][col] = 1 則 row行 col列出現的字母為o(或者O),
把所有處於邊界的o(或者O)加入到queue中，然後就是一個典型的BFS了，只需要循環出隊入隊，並做好標記，如果從隊列中出去的話，證明這個位置一定是沒有被X所包圍的，那麼標記這個位置flags[row][col] = 1;
之後只需要循環flags這個二維數組就可以了。
AC代碼：
public class Solution {
private int[][] flags;//用來標記每個位置的字母
private int rowLength;//行數
private int colLength;//列數
/*自定義放入queue中的數據結構類型*/
class Node{
int i;
int j;
public Node(int i, int j) {
this.i = i;
this.j = j;
}
}
public void solve(char[][] board){
/*初始化*/
rowLength = board.length;
if (rowLength == 0 || board[0].length == 0)
return ;
colLength = board[0].length;
/*初始化flags, queue, 然後把board[][]中的邊界字母為o(或者O)的取出放入queue*/
flags = new int[rowLength][colLength];
Queue queue = new LinkedList();
for (int i=0; i= 0 && (board[row][col-1] == 'o' || board[row][col-1] == 'O' )&& flags[row][col-1] == 0){
queue.add(new Node(row,col-1));
}
//right
if (col+1 < colLength && (board[row][col+1] == 'o' || board[row][col+1] == 'O') && flags[row][col+1] == 0){
queue.add(new Node(row,col+1));
}
//up
if (row-1 >= 0 && (board[row-1][col] == 'o' || board[row-1][col] == 'O')&& flags[row-1][col] == 0){
queue.add(new Node(row-1,col));
}
//down
if (row+1 < rowLength && (board[row+1][col] == 'o' || board[row+1][col] == 'O')&& flags[row+1][col] == 0){
queue.add(new Node(row+1,col));
}
}
/*重新賦值board[][]*/
for (int i=0; i
題目四：
Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
分析：考察的其實就是對平衡二叉樹概念的理解，和二叉樹求深度的方法的掌握
一棵二叉樹如果滿足平衡的條件，那麼包括它自身，和它的任何一個子樹的左右子樹的深度之差必須要小於2，這樣問題就轉換成了遞歸的了，一直遞歸下去，如果不滿足條件，則把全局的標志flag置為false;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private boolean flag = true;
public boolean isBalanced(TreeNode root) {
calDeepthByTree(root);
return flag;
}
public int calDeepthByTree(TreeNode root) {
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
int deepLeft = 0;
int deepRight = 0;
deepLeft = calDeepthByTree(root.left) + 1;
deepRight = calDeepthByTree(root.right) + 1;
if (Math.abs(deepRight - deepLeft) >= 2) {
flag = false;
}
return deepRight > deepLeft ? deepRight : deepLeft;
}
}
題目五：
Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
分析： 給我們一個二叉樹，要求出從根結點到葉子結點的最短的路徑（依舊還是遞歸哈！）
很簡單，直接看代碼：
AC代碼：
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int minDepth(TreeNode root) {
/*遞歸結束條件*/
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
int leftdepth = minDepth(root.left);
int rightdepth = minDepth(root.right);
/*當其中左右子樹有一支是為null的時候，那麼路徑也只有另外一支了，不管多長都只能選那條路了*/
if (leftdepth == 0){
return rightdepth+1;
}
if (rightdepth == 0){
return leftdepth+1;
}
/*返回左右子樹中較小的一邊*/
return leftdepth > rightdepth ? rightdepth + 1 : leftdepth + 1;
}
}
