Python 二叉树leetcode 部分刷题小总结

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