leetCode解题报告5道题(三)

题目一：

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.

分析：层次遍历的变形哈.没啥太大的变化，看代码理解下哈！

题目二：

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代码：

类似的题目：

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.

题意：跟上面的一样，只不过数组换成了链表！！果断要知道如何快速求出链表中间的那个结点哈~

题目三：

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代码：

题目四：

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;

题目五：

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代码：