94. Binary Tree Inorder Traversal

中序 inorder：左節(jié)點(diǎn)－>根節(jié)點(diǎn)－>右節(jié)點(diǎn)

前序 pre-order：根節(jié)點(diǎn)－左節(jié)點(diǎn)－右節(jié)點(diǎn)

后序 post-order: 左節(jié)點(diǎn)－右節(jié)點(diǎn)－根節(jié)點(diǎn)

注意：因?yàn)槊看蝡op出來的是最后一個(gè)元素，所以push時(shí)應(yīng)該按相反的順序來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

給定一個(gè)值n，可以構(gòu)建多少個(gè)存儲(chǔ)1到n的BST? 這題用到了動(dòng)態(tài)規(guī)劃

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

當(dāng)n＝0時(shí)，應(yīng)該返回［］而不是［［］］

98. Validate Binary Search Tree

一個(gè)很重要的性質(zhì)：二叉搜索樹的中序遍歷之后數(shù)值是有序的，所以先進(jìn)行二叉樹中序遍歷，再檢查遍歷的結(jié)果是否有序。但需要注意的是，這道題要求左節(jié)點(diǎn)小于root，root又小于右節(jié)點(diǎn)，都不包含等于。所以最后的判斷條件要用for循環(huán)來兩個(gè)兩個(gè)的進(jìn)行比較。

99. (Hard) Recover Binary Search Tree?

這道題沒有實(shí)現(xiàn)。

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最小整數(shù)：-sys.maxsize-1

100. Same Tree

有recursively和iteratively兩種實(shí)現(xiàn)方法

101. Symmetric Tree

沒有根的時(shí)候，要返回true

recursive方法： 需要注意的一點(diǎn)就是函數(shù)必須傳進(jìn)來root.left和root.right兩個(gè)參數(shù)，不能只傳一個(gè)，因?yàn)橹粋饕粋€(gè)的時(shí)候，你只能比較root.left和root.right是否相等，這種情況只適用于第二層，再往下就不對(duì)了，比如第三層，1，2，2，1 才是對(duì)稱的，需要比較root.left.left 和root.right.right, 以及root.left.right和root.right.left

iterative方法：append的時(shí)候需要注意順序，因?yàn)閜op是最后一個(gè)元素，所以append也要反著來：

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

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

102. Binary Tree Level Order Traversal

注意的點(diǎn)是：res.append([node.val for node in level]) ?這樣就可以把每層的值放在同一個(gè)list里。

這道題的思路是，維護(hù)三個(gè)list，一個(gè)是最后結(jié)果res，一個(gè)是當(dāng)前層level，一個(gè)是下一層next。當(dāng)level存在時(shí)，每次循環(huán)把node.left，node.right存到下一層中，針對(duì)每個(gè)node都這樣做。最后判斷next是否為空，若不為空，就把它傳給level。當(dāng)當(dāng)前層為葉子層時(shí)，下一層就為空

103. Binary Tree Zigzag Level Order Traversal

跟上一題不同的地方就是zigzag，可以用一個(gè)計(jì)數(shù)器，從1開始，當(dāng)計(jì)數(shù)器對(duì)2取余為1時(shí)，便正向賦值，否則就反向賦值：res.append([node.val for node in level[::-1]])

循環(huán)最后應(yīng)該講計(jì)數(shù)器加1

104. Maximum Depth of Binary Tree

Iterative方法：和上幾道題一樣，也是BFS，用兩個(gè)list, 一個(gè)存放當(dāng)前層，一個(gè)存放下一層，如果下一層不為空，depth就加1. depth最開始從1開始，如果要從0開始，就在返回結(jié)果的時(shí)候加1. ?

recursive方法：新建一個(gè)helper函數(shù)，傳進(jìn)去的參數(shù)有node, depth，這里的depth從0開始，不然就會(huì)出錯(cuò)。因?yàn)閔elper里當(dāng)node存在事depth就會(huì)加1. 并且返回用node.left和node.right作為參數(shù)時(shí)的最大值。

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

當(dāng)node不存在，就返回depth

105. Construct Binary Tree from Preorder and Inorder Traversal

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

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

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

注意這里是先賦值left，再賦值right，順序反過來不對(duì)

判斷條件只能是 if inorder:

106. Construct Binary Tree from Inorder and Postorder Traversal

Postorder里最后一個(gè)元素是根, postorder.pop()

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

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

這里是先賦值right，再賦值left，順序不可以反過來

為什么呢？因?yàn)閜op總是pop最右邊的元素，在postorder中，[左，右，根]，當(dāng)根被pop出去之后，下一個(gè)被pop的就是右子樹，所以要先對(duì)root.right進(jìn)行操作

判斷條件只能是 if inorder:

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

一個(gè)方法就是對(duì)原來的level traversal結(jié)果進(jìn)行reverse

另一個(gè)方法就是使用nodelist（stack）, 存放節(jié)點(diǎn)和深度，每次pop出一個(gè)元素，需要注意的是，當(dāng)res的長度小于depth時(shí)，要在res中插入：res.insert(0, [])

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

level從1開始

108. Convert Sorted Array to Binary Search Tree

105和106的簡化版，只給一個(gè)sorted array，因?yàn)锽ST的inorder遍歷是有序數(shù)列，所以每個(gè)數(shù)列的nums[len(nums)/2]為根，再遞歸地調(diào)用原函數(shù)，得到left和right

110. Balanced Binary Tree

這道題用到了求深度的函數(shù)，對(duì)根的左右子樹求深度，看他們的絕對(duì)值是否小于等于1，并且左右子樹是否也是平衡樹，根據(jù)平衡樹的定義可以寫出來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中傳參數(shù)的時(shí)候，root的depth應(yīng)該是0，因?yàn)榇藭r(shí)root已被證實(shí)存在，helper函數(shù)會(huì)將depth加1

2· helper函數(shù)里的判斷條件，要比求最大深度時(shí)多一些。因?yàn)樽钚∩疃鹊亩x是：從根節(jié)點(diǎn)到最近的葉子節(jié)點(diǎn)的最短距離 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。 當(dāng)左節(jié)點(diǎn)不存在，就用右節(jié)點(diǎn)做參數(shù)傳遞到helper中，同時(shí)depth加1，同樣，右節(jié)點(diǎn)不存在時(shí)，用左節(jié)點(diǎn)做參數(shù)。這是因?yàn)?，如果左?jié)點(diǎn)不存在，而右節(jié)點(diǎn)存在，那說明左節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，所以要繼續(xù)右節(jié)點(diǎn)。當(dāng)左右都存在時(shí)，就返回他們的MIN值

** 葉子節(jié)點(diǎn)的度為0！

112. Path Sum

Iterative: 又是樹的路徑問題，維護(hù)一個(gè)nodelist，每個(gè)元素是（node, node,val）, 不斷更新nodelist以及其中的node.val，最后看sum在不在res數(shù)組里。DFS

Recursive: ?當(dāng)沒有根，返回F，當(dāng)沒有左右子樹，根的值又等于sum，返回T。否則就講root.val從sum中減去，成為新的sum，返回以左子樹和新的sum為參數(shù)的遞歸 ?或者以右子樹和新的sum做參數(shù)的遞歸。因?yàn)橹灰幸粋€(gè)為真，結(jié)果就為真，所以是or的關(guān)系

sum -= root.val

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

113. Path Sum II

要求返回滿足和相等的路徑

iterative方法：依然是nodelist，只不過這次的nodelist里每個(gè)元素不再是兩個(gè)參數(shù)，而是三個(gè)，一個(gè)是node, 一個(gè)是node.val， 一個(gè)是[node.val]， 第二個(gè)用來疊加路徑和，第三個(gè)用來存放路徑。注意在更新nodelist時(shí)，第二個(gè)node.val可以直接疊加: value+node.left.val，第三個(gè)要在list的基礎(chǔ)上疊加：path + [node.left.val]，這樣就相當(dāng)于append了

recursive方法：這次的helper函數(shù)用到了四個(gè)參數(shù)，node, sum, path, res，當(dāng)沒有左右子樹且node.val == sum(sum一直在減少)時(shí)，將node.val添加到path中，再將path添加到res中。

如果有左右子樹，就遞歸調(diào)用helper函數(shù)，但是參數(shù)要進(jìn)行更新

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

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

當(dāng)node不存在時(shí)，直接返回

114. Flatten Binary Tree to Linked List

同樣有遞歸和迭代兩種方法，注意的是，在轉(zhuǎn)換成linkedlist時(shí)，root前一定要有一個(gè)pre node來指向root。

Iterative: 依然維護(hù)一個(gè)nodelist，每次從nodeList中pop出來一個(gè)元素，將pre.right指向這個(gè)元素，pre.left = None，pre初始化為任意一個(gè)treenode(pre = TreeNode(-1)). 然后如果node.left存在，將其append進(jìn)nodelist, node.right也同樣。最后將pre = node, 即當(dāng)前的node變?yōu)樾碌膒re. 因?yàn)镻op是取出最后一個(gè)元素，所以要先append node.right, 再append node.left

Recursive: 將pre的初始化寫在__init__函數(shù)里，self.pre = None, 遞歸調(diào)用函數(shù)本身，先以root.right為參數(shù)，再以root.left為參數(shù)。然后將

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

感覺這是dfs, 先進(jìn)入到最后一層，再一層一層向上操作。所以要將root.right指向self.pre，self.pre的初始值為空

116. Populating Next Right Pointers in Each Node

理解題意時(shí)有很重要的一點(diǎn)就是，因?yàn)橐呀?jīng)初始化了所有的node的next指針為null，所以每一行最后邊那個(gè)node是不用管的，它的next已經(jīng)指向了null。

使用一個(gè)pre指針，讓它總是指向root

while循環(huán)的判斷條件為while root.left，因?yàn)槲覀冊(cè)诋?dāng)前行就可以執(zhí)行完下一行的任務(wù)，所以無需將root循環(huán)到最后一行。

if 循環(huán)的判斷語句為if root.next，意思是檢查當(dāng)前root的next是指向空，還是已經(jīng)指向了某個(gè)node，如果它不指向空，我們就root.right.next = root.next.left， 并把root.next作為新的root

如果它指向空，root = pre.left ; ?pre = root； ?我們就把pre.left作為新的root, 即向右移動(dòng)了一個(gè)node。

** 改變r(jià)oot的值時(shí)，一定是要root = pre.left， 不能是root = root.left

**當(dāng)root.next存在時(shí)，證明root.next已經(jīng)指向了某一個(gè)元素，現(xiàn)在就應(yīng)該將root.right.next指向root.next.left， 即將兩個(gè)子樹之間產(chǎn)生聯(lián)系

117. Populating Next Right Pointers in Each Node II

這題是上一題的follow up，上一題假設(shè)了是完美二叉樹，all leaves are at the same level, and every parent has two children，這一題說的是可能是任何二叉樹。

先初始化兩個(gè)TreeLinkNode, tail 和 dummy，root 代表當(dāng)前層的節(jié)點(diǎn)，tail代表下一層的節(jié)點(diǎn)。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轉(zhuǎn)換為數(shù)字，然后求所有path轉(zhuǎn)換之后的總和。求path的過程和之前的題目一樣，但是path不是存成數(shù)組的形式，而是以字符的形式存放，每次更新時(shí)：

path + str(node.left.val) ?注意：1，要用加號(hào) 2，要轉(zhuǎn)換為str形式

最后再將每一個(gè)path轉(zhuǎn)換為int形式再全部相加就可以了

124. Binary Tree Maximum Path Sum

http://www.itdecent.cn/p/c3e81355831d