Binary Tree Preorder Traversal
Binary Tree Inorder Traversal
Binary Tree Postorder Traversal
# 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):
ret,stack = [],[root]
while stack:
node = stack.pop()
if node:
ret.append(node.val)
stack.append(node.right)
stack.append(node.left)
return ret
def inorderTraversal(self, root):
ret,stack = [],[]
while True:
while root:
stack.append(root)
root = root.left
if not stack:return ret
node = stack.pop()
ret.append(node.val)
root=node.right
return ret
# 后序遍历
def postorderTraversal(self, root):
res=[]
self.helper(root,res)
return res
def helper(self,root,res):
if root:
self.helper(root.left,res)
self.helper(root.right,res)
res.append(root.val)
Binary Tree Level Order Traversal
def levelOrder(root):
if not root:return []
res,level = [],[root]
while level:
res.append([n.val for n in level])
temp = []
for i in level:
temp.extend([i.left,i.right])
level = [t for t in temp if t]
return res
Binary Tree Level Order Traversal II
def levelOrderBottom(self, root):
if not root:return []
res,level = [],[root]
while level:
res.append([n.val for n in level])
temp = []
for i in level:
temp.extend([i.left,i.right])
level = [t for t in temp if t]
res.reverse()
return res
class Solution(object):
def __init__(self):
self.n1=None
self.n2=None
self.pre=None
def recoverTree(self, root):
self.dfs(root)
self.n1.val,self.n2.val = self.n2.val,self.n1.val
def dfs(self,root):
if not root:return root
self.dfs(root.left)
if not self.pre:
self.pre =root
else:
if not self.n1 and root.val<self.pre.val:
self.n1 = self.pre
if self.n1 and root.val<self.pre.val:
self.n2 = root
else:
self.pre = root
self.dfs(root.right)
def isSameTree(self, p, q):
if p==None and q==None:
return True
if p and q and p.val==q.val:
return (self.isSameTree(p.left,q.left)) and (self.isSameTree(p.right,q.right))
else :return False
class Solution(object):
def isSymmetric(self, root):
if not root:return True
return self.isMirror(root.left,root.right)
def isMirror(self,left,right):
if left==None and right==None:return True
if left==None or right==None:return False
if left.val == right.val:
outer = self.isMirror(left.left,right.right)
inner = self.isMirror(left.right,right.left)
return outer and inner
else:return False
class Solution(object):
def isBalanced(self, root):
if not root:return True
return abs(self.treeHeight(root.left)-self.treeHeight(root.right))<2 \
and self.isBalanced(root.left) and self.isBalanced(root.right)
def treeHeight(self,root):
if not root :return 0
return 1+max(self.treeHeight(root.left),self.treeHeight(root.right))
Flatten Binary Tree to Linked List
class Solution(object):
def __init__(self):
self.pre=None
def flatten(self, root):
if not root:return None
self.flatten(root.right)
self.flatten(root.left)
root.right = self.pre
root.left = None
self.pre=root
Populating Next Right Pointers in Each Node II
class Solution(object):
def connect(self, root):
if not root:return
queue,nextL = [root],[]
while queue:
cur = queue.pop(0)
if cur.left:
nextL.append(cur.left)
if cur.right:
nextL.append(cur.right)
if queue:
cur.next = queue[0]
if not queue and nextL:
queue,nextL = nextL,queue
Construct Binary Tree from Preorder and Inorder Traversal
class Solution(object):
def buildTree(self, preorder, inorder):
if not preorder:return None
dic={}
for i,v in enumerate(inorder):
dic[v]=i
self.indPre = 0
return self.buildTreeHelper(preorder,0,len(preorder)-1,dic)
def buildTreeHelper(self,preorder,s,e,dic):
if s>e or self.indPre == len(preorder):
return None
root = TreeNode(preorder[self.indPre])
self.indPre+=1
index = dic[root.val]
root.left = self.buildTreeHelper(preorder,s,index-1,dic)
root.right = self.buildTreeHelper(preorder,index+1,e,dic)
return root
Construct Binary Tree from Inorder and Postorder Traversal
class Solution(object):
def buildTree(self, inorder, postorder):
if inorder:
index = inorder.index(postorder.pop())
root = TreeNode(inorder[index])
root.right = self.buildTree(inorder[index+1:],postorder)
root.left = self.buildTree(inorder[:index],postorder)
return root
# 卡特兰数
class Solution(object):
def numTrees(self, n):
res=[0]*(n+1)
res[0]=1
for i in xrange(n+1):
for j in xrange(i):
res[i]+=res[j]*res[i-1-j]
return res[n]
# 先中序，后判断是否是排列好的
class Solution(object):
def isValidBST(self, root):
outOrder = []
self.inorder(root,outOrder)
for i in xrange(len(outOrder)-1):
if outOrder[i]>=outOrder[i+1]:
return False
return True
def inorder(self,root,outOrder):
if not root:return
self.inorder(root.left,outOrder)
outOrder.append(root.val)
self.inorder(root.right,outOrder)
Convert Sorted List to Binary Search Tree
class Solution(object):
def sortedListToBST(self, head):
if not head:return
if not head.next:return TreeNode(head.val)
slow,fast = head,head.next.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
temp = slow.next
slow.next = None
root = TreeNode(temp.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(temp.next)
return root
Convert Sorted Array to Binary Search Tree
class Solution(object):
def sortedArrayToBST(self, num):
if not num:return
mid = len(num)/2
root =TreeNode(num[mid])
root.left = self.sortedArrayToBST(num[:mid])
root.right = self.sortedArrayToBST(num[mid+1:])
return root
class Solution(object):
def hasPathSum(self, root, sum):
if not root :return False
if not root.left and not root.right and root.val == sum:
return True
sum -= root.val
return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)
class Solution(object):
def pathSum(self, root, sum):
ans = []
self.dfs(root,sum,[],ans)
return ans
def dfs(self,root,sum,tmp,ans):
if not root : return
if not root.left and not root.right and root.val == sum:
ans.append(tmp+[root.val])
return
sum-=root.val
self.dfs(root.left,sum,tmp+[root.val],ans)
self.dfs(root.right,sum,tmp+[root.val],ans)
