# leetcode刷题

“追求聪明是一种人生态度”;

Sacha Chua的三字立身哲学: learn–> share–> scale

https://sachachua.com/blog/2012/11/coming-up-with-a-three-word-life-philosophy/

So learn by sharing．

8 个赞

Algorithms.Binary.Search

Sort, Strategy, Solve and Check,

Sort是将题干中所有的条件都列出来, 其余几步后文陆续分享.

(编辑区排版实在不顺手)

Solution

``````  class Solution:
"""
:type n: int
:rtype: int
"""
lo = 1
hi = n -1
while lo < hi:
mid = (lo+hi) // 2
lo = mid + 1
else:
hi = mid
return lo
``````
1 个赞

39道能用二分查找解的题目:

1 个赞

3 个赞

agreed, 就是投石问路, 瞧瞧哪个话题有人气儿.

1 个赞

2 个赞

1 个赞

# Tree Traverse

## pre-order(NLR) 前序遍历

``````preorder(node)
if (node = null)
return
visit(node) # visit在先
preorder(node.left)
preorder(node.right)
``````

## post-order(LRN) 后序遍历

``````postorder(node)
if (node = null)
return
postorder(node.left)
postorder(node.right)
visit(node) # visit在后
``````

## in-order(LNR)中序或者顺序遍历

``````inorder(node)
if (node = null)
return
inorder(node.left)
visit(node)
inorder(node.right)
``````

## Level-order Traversal(层级遍历)

``````levelorder(root)
q ← empty queue
q.enqueue(root)
while not q.isEmpty() do
node ← q.dequeue()
visit(node)
if node.left ≠ null then
q.enqueue(node.left)
if node.right ≠ null then
q.enqueue(node.right)
``````

## ^Summary^,

``````
# Preorder
class Solution1:
def preorderTraversal(self, root: TreeNode) -> "List[int]":
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if root: # 检测的点位
res.append(root.val) #每一个node都是一个root
self.dfs(root.left, res) #left first
self.dfs(root.right, res)

# Inorder
class Solution2:
def inorderTraversal(self, root: "TreeNode") -> "List[int]":
res = []
self.helper(root, res)
return res

def dfs(self, root, res):
if root:
self.dfs(root.left, res)
res.append(root.val) # 在中间添加进来.
self.dfs(root.right, res)

# postorder
class Solution3(object):
def postorderTraversal(self, root):
self.res = []
self.dfs(root)
return self.res

def dfs(self, root):
if not root:
return
self.dfs(root.left)
self.dfs(root.right)
self.res.append(root.val)

``````

## 144.Binary Search Preorder Traversal(前序遍历)

### Problem

Given a binary tree, return the preorder traversal of its nodes' values.

``````Input: [1,null,2,3]
1
\
2
/
3

Output: [1,2,3]
``````

Follow up: Recursive solution is trivial, could you do it iteratively? iterations的方法, 考虑的是如何走下一步.

### Solution

``````# recursion solution
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
#recursilvely
class Solution1:
def preorderTraversal(self, root: TreeNode) -> "List[int]":
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if root: # 检测的点位
res.append(root.val) #每一个node都是一个root
self.dfs(root.left, res) #left first
self.dfs(root.right, res)

# iterative solution
class Solution2:
def preorderTraversal(self, root: TreeNode) -> "List[int]":
stack, res = [root], [] # 简练极了.
while stack:
cur = stack.pop()
if cur:
res.append(cur.val)
#right child is pushed first so that left is processed first
stack.append(cur.right) #the sequence.
# 注意这里的顺序呦吼.
stack.append(cur.left)
return res

#Pseudocodes
iterativePreorder(node)
if (node = null)
return
s ← empty stack
s.push(node)
while (not s.isEmpty())
node ← s.pop()
visit(node)
//right child is pushed first so that left is processed first
if (node.right ≠ null)
s.push(node.right)
if (node.left ≠ null)
s.push(node.left)
``````

### Morris Traversal solution

``````class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
node, output = root, []
while node:
if not node.left:
output.append(node.val)
node = node.right
else:
predecessor = node.left

while predecessor.right and predecessor.right is not node:
predecessor = predecessor.right

if not predecessor.right:
output.append(node.val)
predecessor.right = node
node = node.left
else:
predecessor.right = None
node = node.right

return output
``````

## 145.Binary Tree Postorder Traversal (后续遍历)

### Problem

Given a binary tree, return the postorder traversal of its nodes' values.

``````Input: [1,null,2,3]
1
\
2
/
3

Output: [3,2,1]
``````

Follow up: Recursive solution is trivial, could you do it iteratively?

### Solution

``````class Solution1(object):
def postorderTraversal(self, root):
self.res = []
self.dfs(root)
return self.res

def dfs(self, root):
if not root:
return
self.dfs(root.left)
self.dfs(root.right)
self.res.append(root.val)

# iteration solution
class Solution2(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []

stack, output = [root, ], []
while stack:
root = stack.pop()
output.append(root.val)
if root.left is not None:
stack.append(root.left)
if root.right is not None:
stack.append(root.right)

return output[::-1]

``````

## 94.Binary Tree Inorder Traversal of Binary Tree(中序遍历)

### Problem

Given a binary tree, return the inorder traversal of its nodes' values.

``````Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]
``````

Follow up: Recursive solution is trivial, could you do it iteratively?

### Solution

``````# psudocode
inorder(node)
if (node = null)
return
inorder(node.left)
visit(node)
inorder(node.right)
# recursive solution
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution1:
def inorderTraversal(self, root: "TreeNode") -> "List[int]":
res = []
self.helper(root, res)
return res

def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)

``````
``````# iteratively psudocode
iterativeInorder(node)
s ← empty stack
while (not s.isEmpty() or node ≠ null)
if (node ≠ null)
s.push(node)
node ← node.left
else
node ← s.pop()
visit(node)
node ← node.right

class Solution2: #要将第一个点单独拿出来.
def inorderTraversal(self, root: "TreeNode") -> "List[int]":
res, stack = [], []
cur = root
while cur != None or len(stack) > 0:
# while not ( cur == None and len(stack) ==0): #只要有一个就行.
if cur == None:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
if  cur != None:
stack.append(cur)
cur = cur.left
return res

class Solution3:
def inorderTraversal(self, root: "TreeNode") -> "List[int]":
stack, res = [root], []

while stack:
cur = stack[-1]

if cur != None:
cur = cur.left
if cur != None:
stack.append(cur)
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res

``````

## 102. Binary Tree Level Order Traversal(层序遍历)

### Problem

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

return its level order traversal as:

[ [3], [9,20], [15,7] ]

### Solution

``````class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
from collections import deque
if root == None: return []
queue = deque([root])
res = []
step = -1
while queue:
step += 1
size = len(queue)
if len(res) < step + 1:
res.append([])

for _ in range(size):
cur = queue.popleft()
res[step].append(cur.val)
#stretch
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return res
# 最终实用模板．

``````

## 103. Binary Tree Zigzag Level Order Traversal(层序遍历)

### Problem

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,null,null,15,7],

``````  3
/ \
9  20
/  \
15   7
``````

return its zigzag level order traversal as:

``````[
[3],
[20,9],
[15,7]
]
``````

### Solution

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
res, queue = [], [(root, 0)]
while queue:
curr, level = queue.pop(0)
if curr:
if len(res) < level+1:
res.append([])
if level % 2 == 0:
res[level].append(curr.val)
else:
res[level]
queue.append((curr.left, level+1))
queue.append((curr.right, level+1))
return res
``````