94. Binary Tree Inorder Traversal

中序 inorder：左节点－>根节点－>右节点

前序 pre-order：根节点－左节点－右节点

后序 post-order: 左节点－右节点－根节点

注意：因为每次pop出来的是最后一个元素，所以push时应该按相反的顺序来push

inorder:

nodelist.append((node.right, False))

nodelist.append((node, True))

nodelist.append((node.left, False))

pre-order:

nodelist.append((node.right, False))

nodelist.append((node.left, False))

nodelist.append((node, True))

post-order:

nodelist.append((node, True))

nodelist.append((node.right, False))

nodelist.append((node.left, False))

96. Unique Binary Search Trees

给定一个值n，可以构建多少个存储1到n的BST? 这题用到了动态规划

Suppose you are given 1--n, and you want to generate all binary search trees. How do you do it? Suppose you put number i on the root, then simply 

1. Generate all BST on the left branch by running the same algorithm with 1--(i-1), 

2. Generate all BST on the right branch by running the same algorithm with (i+1)--n.

3. Take all combinations of left branch and right branch, and that's it for i on the root.

Then you let i go from 1 to n.

95. Unique Binary Search Trees II

这题跟96题类似，用的方法是divide and conquer

当n＝0时，应该返回［］而不是［［］］

98. Validate Binary Search Tree

一个很重要的性质：二叉搜索树的中序遍历之后数值是有序的，所以先进行二叉树中序遍历，再检查遍历的结果是否有序。但需要注意的是，这道题要求左节点小于root，root又小于右节点，都不包含等于。所以最后的判断条件要用for循环来两个两个的进行比较。

99. (Hard) Recover Binary Search Tree 

这道题没有实现。

The first element is always larger than its next one while the second element is always smaller than its previous one.

思路来自于：https://discuss.leetcode.com/topic/3988/no-fancy-algorithm-just-simple-and-powerful-in-order-traversal/2

The space usage is O(tree height), which could be O(lgn) in the best case and O(n) for the worst.

**python最小整数：-sys.maxsize-1

100. Same Tree

有recursively和iteratively两种实现方法

101. Symmetric Tree

没有根的时候，要返回true

recursive方法： 需要注意的一点就是函数必须传进来root.left和root.right两个参数，不能只传一个，因为只传一个的时候，你只能比较root.left和root.right是否相等，这种情况只适用于第二层，再往下就不对了，比如第三层，1，2，2，1 才是对称的，需要比较root.left.left 和root.right.right, 以及root.left.right和root.right.left

iterative方法：append的时候需要注意顺序，因为pop是最后一个元素，所以append也要反着来：

p.append(p1.left)  p.append(p1.right)

q.append(q1.right)  q.append(q1.left)

102. Binary Tree Level Order Traversal

注意的点是：res.append([node.val for node in level])  这样就可以把每层的值放在同一个list里。

这道题的思路是，维护三个list，一个是最后结果res，一个是当前层level，一个是下一层next。当level存在时，每次循环把node.left，node.right存到下一层中，针对每个node都这样做。最后判断next是否为空，若不为空，就把它传给level。当当前层为叶子层时，下一层就为空

103. Binary Tree Zigzag Level Order Traversal

跟上一题不同的地方就是zigzag，可以用一个计数器，从1开始，当计数器对2取余为1时，便正向赋值，否则就反向赋值：res.append([node.val for node in level[::-1]])

循环最后应该讲计数器加1

104. Maximum Depth of Binary Tree

Iterative方法：和上几道题一样，也是BFS，用两个list, 一个存放当前层，一个存放下一层，如果下一层不为空，depth就加1. depth最开始从1开始，如果要从0开始，就在返回结果的时候加1.  

recursive方法：新建一个helper函数，传进去的参数有node, depth，这里的depth从0开始，不然就会出错。因为helper里当node存在事depth就会加1. 并且返回用node.left和node.right作为参数时的最大值。

return max(self.helper(node.left, depth), self.helper(node.right, depth))

当node不存在，就返回depth

105. Construct Binary Tree from Preorder and Inorder Traversal

Preorder的第一个元素是根preorder.pop(0)，取得根的index之后：

root.left = self.buildTree(preorder, inorder[:index])

root.right = self.buildTree(preorder, inorder[index+1:])

注意这里是先赋值left，再赋值right，顺序反过来不对

判断条件只能是 if inorder:

106. Construct Binary Tree from Inorder and Postorder Traversal

Postorder里最后一个元素是根, postorder.pop()

root.right = self.buildTree(inorder[:index], postorder)

root.left = self.buildTree(inorder[index+1:], postorder)

这里是先赋值right，再赋值left，顺序不可以反过来

为什么呢？因为pop总是pop最右边的元素，在postorder中，[左，右，根]，当根被pop出去之后，下一个被pop的就是右子树，所以要先对root.right进行操作

判断条件只能是 if inorder:

107. Binary Tree Level Order Traversal II （bottom-up）

一个方法就是对原来的level traversal结果进行reverse

另一个方法就是使用nodelist（stack）, 存放节点和深度，每次pop出一个元素，需要注意的是，当res的长度小于depth时，要在res中插入：res.insert(0, [])

向nodelist中添加元素需要注意顺序，如果先左后右，就要pop(0)，如果先右后左，就直接pop()

level从1开始

108. Convert Sorted Array to Binary Search Tree

105和106的简化版，只给一个sorted array，因为BST的inorder遍历是有序数列，所以每个数列的nums[len(nums)/2]为根，再递归地调用原函数，得到left和right

110. Balanced Binary Tree

这道题用到了求深度的函数，对根的左右子树求深度，看他们的绝对值是否小于等于1，并且左右子树是否也是平衡树，根据平衡树的定义可以写出来return语句

`return abs(self.helper(root.left, 1) - self.helper(root.right, 1)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)`

111. Minimum Depth of Binary Tree

要注意的地方 1· 向helper中传参数的时候，root的depth应该是0，因为此时root已被证实存在，helper函数会将depth加1

2· helper函数里的判断条件，要比求最大深度时多一些。因为最小深度的定义是：从根节点到最近的叶子节点的最短距离 The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 所以判断条件里要有，if not node.left

if not node.right。 当左节点不存在，就用右节点做参数传递到helper中，同时depth加1，同样，右节点不存在时，用左节点做参数。这是因为，如果左节点不存在，而右节点存在，那说明左节点不是叶子节点，所以要继续右节点。当左右都存在时，就返回他们的MIN值

** 叶子节点的度为0！

112. Path Sum

Iterative: 又是树的路径问题，维护一个nodelist，每个元素是（node, node,val）, 不断更新nodelist以及其中的node.val，最后看sum在不在res数组里。DFS

Recursive:  当没有根，返回F，当没有左右子树，根的值又等于sum，返回T。否则就讲root.val从sum中减去，成为新的sum，返回以左子树和新的sum为参数的递归  或者以右子树和新的sum做参数的递归。因为只要有一个为真，结果就为真，所以是or的关系

sum -= root.val

return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

113. Path Sum II

要求返回满足和相等的路径

iterative方法：依然是nodelist，只不过这次的nodelist里每个元素不再是两个参数，而是三个，一个是node, 一个是node.val， 一个是[node.val]， 第二个用来叠加路径和，第三个用来存放路径。注意在更新nodelist时，第二个node.val可以直接叠加: value+node.left.val，第三个要在list的基础上叠加：path + [node.left.val]，这样就相当于append了

recursive方法：这次的helper函数用到了四个参数，node, sum, path, res，当没有左右子树且node.val == sum(sum一直在减少)时，将node.val添加到path中，再将path添加到res中。

如果有左右子树，就递归调用helper函数，但是参数要进行更新

self.helper(node.left, sum - node.val, path + [node.val], res)

self.helper(node.right, sum - node.val, path + [node.val], res)

当node不存在时，直接返回

114. Flatten Binary Tree to Linked List

同样有递归和迭代两种方法，注意的是，在转换成linkedlist时，root前一定要有一个pre node来指向root。

Iterative: 依然维护一个nodelist，每次从nodeList中pop出来一个元素，将pre.right指向这个元素，pre.left = None，pre初始化为任意一个treenode(pre = TreeNode(-1)). 然后如果node.left存在，将其append进nodelist, node.right也同样。最后将pre = node, 即当前的node变为新的pre. 因为Pop是取出最后一个元素，所以要先append node.right, 再append node.left

Recursive: 将pre的初始化写在__init__函数里，self.pre = None, 递归调用函数本身，先以root.right为参数，再以root.left为参数。然后将

root.right = self.pre,  root.left = None,    self.pre = root.   

感觉这是dfs, 先进入到最后一层，再一层一层向上操作。所以要将root.right指向self.pre，self.pre的初始值为空

116. Populating Next Right Pointers in Each Node

理解题意时有很重要的一点就是，因为已经初始化了所有的node的next指针为null，所以每一行最后边那个node是不用管的，它的next已经指向了null。

使用一个pre指针，让它总是指向root

while循环的判断条件为while root.left，因为我们在当前行就可以执行完下一行的任务，所以无需将root循环到最后一行。

if 循环的判断语句为if root.next，意思是检查当前root的next是指向空，还是已经指向了某个node，如果它不指向空，我们就root.right.next = root.next.left， 并把root.next作为新的root

如果它指向空，root = pre.left ;  pre = root；  我们就把pre.left作为新的root, 即向右移动了一个node。

** 改变root的值时，一定是要root = pre.left， 不能是root = root.left

**当root.next存在时，证明root.next已经指向了某一个元素，现在就应该将root.right.next指向root.next.left， 即将两个子树之间产生联系

117. Populating Next Right Pointers in Each Node II

这题是上一题的follow up，上一题假设了是完美二叉树，all leaves are at the same level, and every parent has two children，这一题说的是可能是任何二叉树。

先初始化两个TreeLinkNode, tail 和 dummy，root 代表当前层的节点，tail代表下一层的节点。while root：让tail.next指向root.left，然后判断tail.next是否存在，若存在，就将tail向后移，tail = tail.next， 然后将tail.next指向root.right，再次判断tail.next是否存在，若存在就向后移，然后让root = root.next，判断root是否还存在，若为空了，则将dummy赋值给tail, 将dummy.next指向root

129. Sum Root to Leaf Numbers

将path转换为数字，然后求所有path转换之后的总和。求path的过程和之前的题目一样，但是path不是存成数组的形式，而是以字符的形式存放，每次更新时：

path + str(node.left.val)  注意：1，要用加号 2，要转换为str形式

最后再将每一个path转换为int形式再全部相加就可以了

124. Binary Tree Maximum Path Sum

http://www.jianshu.com/p/c3e81355831d