1.二叉树前.中.后序遍历
1）递归
建议递归从小到大的思考方向，如中序遍历，先左子树回到根节点，最后到右子树，先底再头最后底
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def qian(self, root):
def a(root,x):
if root:
x.append(root.val)
a(root.left,x）
a(root.right,x)
return x
return a(root,[])
class Solution(object):
def zhong(self, root):
def a(root,x):
if root:
a(root.left,x）
x.append(root.val)
a(root.right,x)
return x
return a(root,[])
class Solution(object):
def hou(self, root):
def a(root,x):
if root:
a(root.left,x）
a(root.right,x)
x.append(root.val)
return x
return a(root,[])
2）迭代遍历
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def preorderTraversal(self, root): #前序遍历
stack = [root]
chuli = []
while stack:
node = stack.pop()
if node:
chuli.append(node.val)
if node.right: #右先进栈
stack.append(node.right)
if node.left:
stack.append(node.left)
return chuli
class Solution(object):
def preorderTraversal(self, root): #后序遍历 为中右左的颠倒
stack = [root]
chuli = []
while stack:
node = stack.pop()
if node:
chuli.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return chuli[::-1] #最后的chuli返回的是中右左的顺序
class Solution(object):
def preorderTraversal(self, root): #中序遍历
stack = []
Val = []
cur = root
while stack or cur:
while cur: #停止循环条件为左节点不存在，即使原先为右节点也已保存
stack.append(cur)
cur = cur.left
cur = stack.pop()
Val.append(cur.val)
cur = cur.right
return Val
2.相同的树
1）迭代遍历
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isSameTree(self, p, q):
stack1 = [p]
stack2 = [q]
baochu1 = []
baochu2 = []
while stack1:
node = stack1.pop()
if node:
baochu1.append(node.val)
if node.right:
stack1.append(node.right)
else:
baochu1.append('1')
if node.left:
stack1.append(node.left)
else:
baochu1.append('2')
while stack2:
node = stack2.pop()
if node:
baochu2.append(node.val)
if node.right:
stack2.append(node.right)
else:
baochu2.append('1')
if node.left:
stack2.append(node.left)
else:
baochu2.append('2')
return baochu1 == baochu2
3.对称二叉树
1）迭代遍历
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isSymmetric(self, root):
if root is None or (root.right is None and root.left is None):
return True
q = [(root.left,root.right)]
while q:
left,right = q.pop(0)
if left is None and right is None:
continue
if left is None or right is None:
return False
if left.val != right.val:
return False
q.append((left.left,right.right))
q.append((left.right,right.left))
return True
4.二叉树的最大深度和最小深度
最大深度：
1）递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object): #利用递归从底至上的返回
def maxDepth(self, root):
if root is None:
return 0
return max(self.maxDepth(root.left, root),self.maxDepth(root.right, root)) + 1
2）迭代遍历
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def maxDepth(self, root): #利用队列先进先出的特点，层遍历，把每一层的节点都遍历完
if root is None:
return 0
depth = 0
queue = [root]
while queue: #遍历所有的节点
changdu = len(queue) #用来记录每一层的节点数
while changdu > 0 :
node = queue.pop(0)
changdu -= 1
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1 #层遍历结束
return depth
最小深度：
1）递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None: #根节点为空
return 0
if root.left is None and root.right is None: #左右节点为空
return 1
if root.left is None or root.right is None: #左节点 右节点任一为空
return self.minDepth(root.left) + self.minDepth(root.right) + 1
return min(self.minDepth(root.left),self.minDepth(root.right)) + 1 #默认树完整
小提示：
需要加self
1、方法自身间的回溯需要加self
2、同一个类，不同对象间的互相调用回溯需要加self
不需要加self
1、方法内的函数递归自身不需要self
