https://leetcode.com/problems/binary-tree-preorder-traversal/#/description
Recursive solution is trivial, could you do it iteratively?
In [4]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans = []
if not root:
return ans
# iterative
stack = [root]
while stack:
node = stack.pop()
ans += [node.val]
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return ans
# recursive
ans.append(root.val)
ans += self.preorderTraversal(root.left)
ans += self.preorderTraversal(root.right)
return ans
https://leetcode.com/problems/binary-tree-inorder-traversal/#/description
Given a binary tree, return the inorder traversal of its nodes' values.
For example: Given binary tree [1,null,2,3], 1 \ 2 / 3 return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
In [5]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans = []
if root is None:
return ans
# iterative
stack = []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return ans
node = stack.pop()
ans.append(node.val)
root = node.right
# recursive
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
https://leetcode.com/problems/binary-tree-postorder-traversal/#/description
Note: Recursive solution is trivial, could you do it iteratively?
In [6]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans = []
if root is None:
return ans
# iterative
stack, lastVist = [root], root
while stack:
top = stack[-1]
if (not top.left and not top.right) or top.left == lastVist or top.right == lastVist:
lastVist = stack.pop()
ans.append(lastVist.val)
else:
if top.right:
stack.append(top.right)
if top.left:
stack.append(top.left)
return ans
# recursive
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
比较快速排序与归并排序的联系与区别：
时间复杂度：都是 O(nlogn) 但是快速排序是平均 O(nlogn)，归并排序是最好最坏都是 O(nlogn)
空间复杂度：快速排序耗费 O(1) 的额外空间，归并排序不得不耗费 O(n) 的额外空间。
排序稳定性：快速排序是不稳定的排序算法。归并排序是稳定的排序算法。http://baike.baidu.com/view/547325.htm
分治的思想：快速排序先整体有序再局部有序。归并排序先局部有序再整体有序。
In [7]:
## Quick Sort
class Solution:
# @param {int[]} A an integer array
# @return nothing
def sortIntegers2(self, A):
# Write your code here
def quicksort(A, start, end):
if start >= end:
return
left, right = start, end
# pivot, the middle value, not A[0], A[-1]
pivot = A[start + (end-start)/2] # get the value not the index
while left <= right: # here is left <= right, not <, aviod overflow!!
while left <= right and A[left] < pivot: # here is A[left] < pivot, not <=, allocation is more homogeneous
left += 1
while left <= right and A[right] > pivot:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
quicksort(A, start, right)
quicksort(A, left, end)
if A is None or len(A) == 0:
return
quicksort(A, 0, len(A)-1)
In [8]:
## Merge Sort
class Solution:
# @param {int[]} A an integer array
# @return nothing
def sortIntegers2(self, A):
# Write your code here
def mergeSort(A, start, end, temp):
if start >= end:
return
mergeSort(A, start, (start + end)/2, temp)
mergeSort(A, (start + end)/2 + 1, end, temp)
merge(A, start, end, temp)
def merge(A, start, end, temp):
mid = (start + end)/2
leftstart, rightstart = start, mid+1
tempstart = start
while leftstart <= mid and rightstart <= end:
if A[leftstart] <= A[rightstart]:
temp[tempstart] = A[leftstart]
leftstart += 1
else:
temp[tempstart] = A[rightstart]
rightstart += 1
tempstart += 1
while leftstart <= mid:
temp[tempstart] = A[leftstart]
leftstart += 1
tempstart += 1
while rightstart <= end:
temp[tempstart] = A[rightstart]
rightstart += 1
tempstart += 1
for i in xrange(start, end+1):
A[i] = temp[i]
if A is None or len(A) == 0:
return
temp = [0 for i in A]
mergeSort(A, 0, len(A)-1, temp)
Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.
https://www.lintcode.com/en/problem/minimum-subtree/
Example Given a binary tree:
1
/ \ -5 2 / \ / \ 0 2 -4 -5 return the node 1.
In [9]:
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
class Solution:
# @param {TreeNode} root the root of binary tree
# @return {TreeNode} the root of the minimum subtree
def __init__(self):
self.node = None
self.minsum = 0x7FFFFFFF
def findSubtree(self, root):
# Write your code here
def helper(root):
if not root:
return 0
newsum = helper(root.left) + helper(root.right) + root.val
if newsum < self.minsum:
self.minsum = newsum
self.node = root
return newsum
helper(root)
return self.node
https://www.lintcode.com/en/problem/subtree-with-maximum-average/
In [2]:
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
class Solution:
# @param {TreeNode} root the root of binary tree
# @return {TreeNode} the root of the maximum average of subtree
node, average = None, -0x80000000 ## note this value!!
def findSubtree2(self, root):
# Write your code here
self.helper(root)
return self.node
def helper(self, root):
if not root:
return 0, 0
left_sum, left_size = self.helper(root.left)
right_sum, right_size = self.helper(root.right)
sum = left_sum + right_sum + root.val
size = left_size + right_size + 1
ave = sum*1.0 / size
if ave >= self.average:
self.average = ave
self.node = root
return sum, size
In [3]:
## instead of using minimun value!!
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
class Solution:
# @param {TreeNode} root the root of binary tree
# @return {TreeNode} the root of the maximum average of subtree
node, average = None, 0
def findSubtree2(self, root):
# Write your code here
self.helper(root)
return self.node
def helper(self, root):
if not root:
return 0, 0
left_sum, left_size = self.helper(root.left)
right_sum, right_size = self.helper(root.right)
sum = left_sum + right_sum + root.val
size = left_size + right_size + 1
ave = sum*1.0 / size
if self.node is None or ave >= self.average:
self.average = ave
self.node = root
return sum, size
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/#/description
In [4]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
if root is None:
return
self.flatten(root.left)
self.flatten(root.right)
p = root
if p.left is None:
return
p = p.left
while p.right:
p = p.right
p.right = root.right
root.right = root.left
root.left = None
Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.
The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.
https://www.lintcode.com/en/problem/lowest-common-ancestor/
Example For the following binary tree:
4 / \ 3 7 / \ 5 6 LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
In [5]:
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
import copy
class Solution:
"""
@param root: The root of the binary search tree.
@param A and B: two nodes in a Binary.
@return: Return the least common ancestor(LCA) of the two nodes.
"""
def lowestCommonAncestor(self, root, A, B):
# write your code here
if not root or root == A or root == B:
return root
left = self.lowestCommonAncestor(root.left, A, B)
right = self.lowestCommonAncestor(root.right, A, B)
if left and right:
return root
if left:
return left
if right:
return right
return None
https://www.lintcode.com/en/problem/lowest-common-ancestor-ii/
In [6]:
"""
Definition of ParentTreeNode:
class ParentTreeNode:
def __init__(self, val):
self.val = val
self.parent, self.left, self.right = None, None, None
"""
class Solution:
"""
@param root: The root of the tree
@param A and B: Two node in the tree
@return: The lowest common ancestor of A and B
"""
def lowestCommonAncestorII(self, root, A, B):
# Write your code here
if not root:
return root
dic = {}
while A:
dic[A] = True
A = A.parent
while B:
if B in dic:
return B
B = B.parent
https://www.lintcode.com/en/problem/lowest-common-ancestor-iii/
In [7]:
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
import copy
class Solution:
"""
@param {TreeNode} root The root of the binary tree.
@param {TreeNode} A and {TreeNode} B two nodes
@return Return the LCA of the two nodes.
"""
def lowestCommonAncestor3(self, root, A, B):
# write your code here
node, a, b = self.helper(root, A, B)
return node
def helper(self, root, A, B):
if root is None:
return None, False, False
leftNode, leftA, leftB = self.helper(root.left, A, B)
rightNode, rightA, rightB = self.helper(root.right, A, B)
a = leftA or rightA or root == A
b = leftB or rightB or root == B
if not a or not b:
return None, a, b
elif leftNode:
return leftNode, a, b
elif rightNode:
return rightNode, a, b
else:
return root, a, b
http://www.lintcode.com/en/problem/binary-tree-longest-consecutive-sequence/
In [8]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root the root of binary tree
# @return {int} the length of the longest consecutive sequence path
def longestConsecutive(self, root):
# Write your code here
start, longest = self.helper(root)
return longest
def helper(self, root):
if root is None:
return 0, 0
left_start, left_longest = self.helper(root.left)
right_start, right_longest = self.helper(root.right)
if root.left and root.val+1 == root.left.val:
if left_start:
left_start += 1
else:
left_start = 2
left_longest = max(left_start, left_longest)
else:
left_start = 0
if root.right and root.val+1 == root.right.val:
if right_start:
right_start += 1
else:
right_start = 2
right_longest = max(right_start, right_longest)
else:
right_start = 0
return max(left_start, right_start), max(left_longest, right_longest, 1)
In [9]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root the root of binary tree
# @return {int} the length of the longest consecutive sequence path
longest = 0
def longestConsecutive(self, root):
# Write your code here
self.helper(root)
return self.longest
def helper(self, root):
if root is None:
return 0
left = self.helper(root.left)
right = self.helper(root.right)
sublongest = 1
if root.left and root.val + 1 == root.left.val:
sublongest = max(sublongest, left+1)
if root.right and root.val + 1 == root.right.val:
sublongest = max(sublongest, right+1)
self.longest = max(self.longest, sublongest)
return sublongest
Given a binary tree, find the length of the longest consecutive sequence path. The path could be start and end at any node in the tree
In [1]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root the root of binary tree
# @return {int} the length of the longest consecutive sequence path
def longestConsecutive2(self, root):
# Write your code here
longest, _, _, = self.helper(root)
return longest
def helper(self, root):
if root is None:
return 0, 0, 0
left_len, left_down, left_up = self.helper(root.left)
right_len, right_down, right_up = self.helper(root.right)
down, up = 0, 0
if root.left is not None and root.left.val + 1 == root.val:
down = max(down, left_down + 1)
if root.left is not None and root.left.val - 1 == root.val:
up = max(up, left_up + 1)
if root.right is not None and root.right.val + 1 == root.val:
down = max(down, right_down + 1)
if root.right is not None and root.right.val - 1 == root.val:
up = max(up, right_up + 1)
len = down + up + 1
len = max(len, left_len, right_len)
return len, down, up
It's follow up problem for Binary Tree Longest Consecutive Sequence II
Given a k-ary tree, find the length of the longest consecutive sequence path. The path could be start and end at any node in the tree
In [2]:
# Definition for a multi tree node.
# class MultiTreeNode(object):
# def __init__(self, x):
# self.val = x
# children = [] # children is a list of MultiTreeNode
class Solution:
# @param {MultiTreeNode} root the root of k-ary tree
# @return {int} the length of the longest consecutive sequence path
def longestConsecutive3(self, root):
# Write your code here
longest, _, _ = self.helper(root)
return longest
def helper(self, root):
if root is None:
return 0, 0, 0
len, down, up = 0, 0, 0
for child in root.children:
clen, cdown, cup = self.helper(child)
if child.val + 1 == root.val:
down = max(down, cdown + 1)
if child.val - 1 == root.val:
up = max(up, cup + 1)
len = max(len, clen)
len = max(len, down + up + 1)
return len, down, up
Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.
A valid path is from root node to any of the leaf nodes.
In [10]:
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
# @param {TreeNode} root the root of binary tree
# @param {int} target an integer
# @return {int[][]} all valid paths
def binaryTreePathSum(self, root, target):
# Write your code here
if root is None:
return []
if root.left is None and root.right is None and root.val == target:
return [[root.val]]
left = self.binaryTreePathSum(root.left, target - root.val)
right = self.binaryTreePathSum(root.right, target - root.val)
paths = []
for p in left:
paths += [[root.val] + p]
for p in right:
paths += [[root.val] + p]
return paths
Your are given a binary tree in which each node contains a value. Design an algorithm to get all paths which sum to a given value. The path does not need to start or end at the root or a leaf, but it must go in a straight line down.
In [8]:
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
# @param {TreeNode} root the root of binary tree
# @param {int} target an integer
# @return {int[][]} all valid paths
def binaryTreePathSum2(self, root, target):
# Write your code here
path, result = [], []
self.dfs(root, path, result, 0, target)
return result
def dfs(self, root, path, result, l, target):
if root is None:
return
path.append(root.val)
temp = target
for i in xrange(l, -1, -1):
temp -= path[i]
if temp == 0:
result.append(path[i:])
self.dfs(root.left, path, result, l + 1, target)
self.dfs(root.right, path, result, l + 1, target)
path.pop()
Give a binary tree, and a target number, find all path that the sum of nodes equal to target, the path could be start and end at any node in the tree.
http://www.lintcode.com/en/problem/binary-tree-path-sum-iii/
In [ ]:
In [11]:
## brilliant solver!!
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: True if the binary tree is BST, or false
"""
def isValidBST(self, root):
# write your code here
return self.helper(root, -0x80000000-1, 0x7FFFFFFF+1)
def helper(self, root, min, max):
if root is None:
return True
elif root.val <= min or root.val >= max:
return False
else:
return self.helper(root.left, min, root.val) \
and self.helper(root.right, root.val, max)
In [ ]: