-
第 21 楼 / webdriver
- 时间: 2014-9-29 23:45算法问题推荐解法来了...
1. Use queue. In order to seperate the levels, use 'NULL' as the end indicator of one level.
2. DFS.
解法（Python）
代码: class Solution:
def levelOrder(self, root):
if root is None:
return []
current, res = [root], []
while current:
next, vals = [], []
for node in current:
vals.append(node.val)
if node.left:
next.append(node.left)
if node.right:
next.append(node.right)
res.append(vals)
current = next
return res
# def levelOrder(self, root):
# """ Using a queue is also fine.
# """
# if root is None:
# return []
# current, res = [root], []
# while current:
# vals, length = [], len(current)
# for i in range(length):
# node = current[0]
# vals.append(node.val)
# if node.left:
# current.append(node.left)
# if node.right:
# current.append(node.right)
# current.pop(0)
# res.append(vals)
# return res -
-
- 时间: 2014-9-29 23:47
-
-
- 时间: 2014-9-29 23:49算法问题推荐解法来了...
Recursion...
解法（Python）
代码: class Solution:
maxSum = -2147483648
def maxPathSum(self, root):
self.maxPathRecur(root)
return self.maxSum
def maxPathRecur(self, root):
if root == None:
return 0
left = max(0, self.maxPathRecur(root.left))
right = max(0, self.maxPathRecur(root.right))
self.maxSum = max(self.maxSum, left + right + root.val)
return root.val + max(left, right) -
- 时间: 2014-9-29 23:49
-
- 时间: 2014-9-29 23:50算法问题推荐解法来了...
1. Iterative way (stack). Time: O(n), Space: O(n).
2. Recursive solution. Time: O(n), Space: O(n).
3. Threaded tree (Morris). Time: O(n), Space: O(1).
You may refer to my blog for more detailed explanations:
www.cnblogs.com/AnnieK...ersal.html
解法（Python）
代码: class Solution:
def postorderTraversal(self, root):
res, stack, current, prev = [], [], root, None
while stack or current:
if current:
stack.append(current)
current = current.left
else:
parent = stack[-1]
if parent.right in (None, prev):
prev = stack.pop()
res.append(prev.val)
else:
current = parent.right
return res -
- 时间: 2014-9-29 23:50
-
- 时间: 2014-9-29 23:51算法问题推荐解法来了...
1. Iterative way (stack). Time: O(n), Space: O(n).
2. Recursive solution. Time: O(n), Space: O(n).
3. Threaded tree (Morris). Time: O(n), Space: O(1).
解法（Python）
代码: class Solution:
def preorderTraversal(self, root):
res, stack = [], [root]
if root is None:
return res
while stack:
current = stack.pop()
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
res.append(current.val)
return res -
- 时间: 2014-9-29 23:52S算法问题: 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]
] -
- 时间: 2014-9-29 23:53算法问题推荐解法来了...
1. Queue + reverse.
2. Two stacks.
3. Vector. Contributed by yinlinglin.
解法（Python）
代码: class Solution:
def zigzagLevelOrder(self, root):
result = []
if root == None:
return result
current, reverse = [root], 0
while len(current) > 0:
# Python is just so slow, but who I can complain? I have to write following code to optimize for skewed tree
# -- None of the code from this tag to the next tag is actually needed -- #
if len(current) == 1 and (current[0].left == None or current[0].right== None):
this_node = current[0]
result.append([this_node.val])
if this_node.left == None and this_node.right != None:
current = [this_node.right]
elif this_node.left != None and this_node.right == None:
current = [this_node.left]
else:
current.pop(0)
else:
# -- None of the code above this tag up to the previous tag is actually needed -- #
vals = []
size = len(current)
for i in range(size):
this_node = current[0]
if reverse:
vals.insert(0, this_node.val)
else:
vals.append(this_node.val)
if i < len(current) - 1:
this_node.next = current[i+1]
if this_node.left != None:
current.append(this_node.left)
if this_node.right != None:
current.append(this_node.right)
current.pop(0)
result.append(vals)
reverse = 1 - reverse
return result -
- 时间: 2014-9-29 23:54S算法问题: Candy
问题描述:
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
Leetcode Hacking Practice -- Solution in Python Part 1
