给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

3

/ \

9 20

/ \

15 7

返回其自底向上的层次遍历为：

[

[15,7],

[9,20],

[3]

]

与[二叉树的最大深度](二叉树的最大深度.md)做法相似，遍历二叉树

广度优先搜索：

* 队列存放当前层所有节点

* 每次拓展下一层的时候，需要将当前队列中所有节点都取出来进行拓展

* 保证每次拓展完时候，队列中存放的都是当前层的所有节点

* 用列表保存每层的元素值

def levelOrderBottom(root):

if not root:

return []

queue_ = Queue()

queue_.put(root)

result = []

while queue_.qsize():

size = queue_.qsize()

vals = [] # 用列表保存每层的节点值

for _ in range(size):

node = queue_.get()

vals.append(node.val)

left = node.left

right = node.right

if left:

queue_.put(left)

if right:

queue_.put(right)

result.append(vals)

result.reverse()

return result

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

叶子节点是指没有子节点的节点。

返回它的最大深度 3 。

3

/ \

9 20

/ \

15 7

递归： 最大深度 = max(左子树最大深度，右子树最大深度) + 1

def maxDepth(root):

if not root:

return 0

max_depth_of_subtree = max(maxDepth(root.left), maxDepth(root.right))

return 1 + max_depth_of_subtree

广度优先搜索：

* 队列存放当前层所有节点

* 每次拓展下一层的时候，需要将当前队列中所有节点都取出来进行拓展

* 保证每次拓展完时候，队列中存放的都是当前层的所有节点

* 用一个变量维护拓展的次数

def maxDepth(root):

if not root:

return 0

depth = 0

queue_ = Queue()

queue_.put(root)

while queue_.qsize():

depth += 1

size = queue_.qsize()

for _ in range(size):

node = queue_.get()

left = node.left

right = node.right

if left:

queue_.put(left)

if right:

queue_.put(right)

return depth

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

0

/ \

-3 9

/ /

-10 5

* 选择列表中间数字作为二叉搜索树的根节点，这样分给左右子树的数字个数相同或只相差1，可以使得树保持平衡。

* 把列表从中间元素分成左右两个列表，分别对应根节点的左子树与右子树

* 递归

def sortedArrayToBST(nums):

if not nums:

return

length = len(nums)

middle = length // 2

root = TreeNode(nums[middle])

left = sortedArrayToBST(nums[:middle])

right = sortedArrayToBST(nums[middle + 1:])

if left:

root.left = left

if right:

root.right = right

return root