前几天貌似怠惰了呢，今天做了几道水题，（bin tree的），放上来。
111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
root_list = [root]
res = []
depth = 1
flag = 0
while root_list:
node_list = []
for i in root_list:
if not i.left and not i.right:
flag = 1
if i.left:
node_list.append(i.left)
if i.right:
node_list.append(i.right)
root_list = node_list
if flag == 1:
return depth
depth += 1
112. Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if root == None:
return False
elif root.left == None and root.right == None and root.val == sum:
return True
return True if self.hasPathSum(root.left,sum - root.val) or self.hasPathSum(root.right,sum - root.val) else False
226. Invert Binary Tree
Invert a binary tree.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root == None:
return root
left = root.left
root.left = self.invertTree(root.right)
root.right = self.invertTree(left)
return root
101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None:
return True
return self.is_balance(root.left,root.right)
def is_balance(self,left,right):
if left == None and right == None:
return True
elif left != None and right != None:
return True if left.val == right.val and self.is_balance(left.right,right.left) and self.is_balance(right.right,left.left) else False
else:
return False
95. Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.
运用动态规划，每次选取一个节点作为根节点，将树分为左右两个子树，直到该子树为空。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0:
return []
return self.createTrees(1,n)
def createTrees(self,start,end):
results = []
if start > end:
results.append(None)
return results
for k in range(start,end+1):
left = self.createTrees(start,k-1)
right = self.createTrees(k+1,end)
for i in left:
for j in right:
root = TreeNode(k)
root.left = i
root.right = j
results.append(root)
return results
105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
return self.build_tree(preorder,0,len(preorder)-1,inorder,0,len(inorder)-1)
def build_tree(self,perorder,pleft,pright,inorder,ileft,iright):
if pleft > pright or ileft > iright:
return None
for i in range(ileft,iright+1):
if perorder[pleft] == inorder[i]:
break
root = TreeNode(perorder[pleft])
root.left = self.build_tree(perorder,pleft+1,pleft+i-ileft,inorder,ileft,i-1)
root.right = self.build_tree(perorder,pleft+i-ileft+1,pright,inorder,i+1,iright)
return root
106. Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
return self.built_tree(inorder,0,len(inorder)-1,postorder,0,len(postorder)-1)
def built_tree(self,inorder,ileft,iright,postorder,pleft,pright):
if ileft > iright or pleft > pright:
return None
root = TreeNode(postorder[pright])
for i in range(ileft,len(inorder)):
if inorder[i] == root.val:
break
root.left = self.built_tree(inorder,ileft,i-1,postorder,pleft,pleft+i-ileft-1)
root.right = self.built_tree(inorder,i+1,iright,postorder,pleft+i-ileft,pright-1)
return root
113. Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
Note: A leaf is a node with no children.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.All_list = []
self.num_list = []
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if root == None:
return self.All_list
self.num_list.append(root.val)
sum -= root.val
if root.left == None and root.right == None and sum == 0:
self.All_list.append(self.num_list.copy())
self.pathSum(root.left, sum)
self.pathSum(root.right, sum)
self.num_list.pop()
return self.All_list
114. Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
if root == None:
return None
if root.left != None:
self.flatten(root.left)
if root.right != None:
self.flatten(root.right)
temp = root.right
root.right = root.left
root.left = None
while root.right != None:
root = root.right
root.right = temp
近期评论