力扣刷题-python-二叉树-1（三种遍历方法 递归、 迭代 、全模板）

1.二叉树

二叉树分为满二叉树和完全二叉树
1）满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
度为0说明孩子节点为0，度为2说明孩子节点为2

、
这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。
2）完全二叉树
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h -1 个节点。

3)二叉搜索数
左边孩子节点比父节点小，右边孩子节点比父节点大。

4)平衡搜索二叉树
左右两个子树不能超过1，同样子树也是平衡二叉树

5）储存方式
分为链表式和顺序式，链表式是分散式存储

2.遍历方式

1.深度优先遍历（DFS）：类似于树中的先序遍历，整体思想是：先输出当前结点，在根据一定的次序去递归查找孩子。
2. 广度优先遍历（BFS）：类似于树中的层次遍历，需要用队列来体现结点访问的次序关系。

深度遍历的拓展
前序遍历（递归法，迭代法）
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）

3.python二叉树储存方法

class TreeNode: 
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
1
2
3
4
5

3.递归遍历

递归三要素
1）确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2）确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3）确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        #中左右
        res= []
        def traversal(noder):
            if not noder:return 
            res.append (noder.val)
            traversal(noder.left)
            traversal(noder.right)
        traversal(root)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

145. 二叉树的后序遍历 - 力扣（LeetCode） (leetcode-cn.com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # 左右中

        res=[]
        def Traversal(noder):
            if not noder:return
            Traversal(noder.left)  #左右
            Traversal(noder.right)
            res.append(noder.val)
        Traversal(root)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

94. 二叉树的中序遍历 - 力扣（LeetCode） (leetcode-cn.com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        #左中右
        def traversal(noder):
            if not noder:return 
            traversal(noder.left)
            res.append(noder.val)
            traversal(noder.right)
        res= []
        traversal(root)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4.迭代遍历（应用栈）

144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
         if not root:return []
         #中左右  迭代法
         stacker = [root]  #栈用于存放节点
         res = []          #保存结果
         while stacker:
             noder = stacker.pop()
             res.append(noder.val)  #首先存放中
             if noder.right:       #因为栈是先进后出 所以先放右
                  stacker.append(noder.right)
             if noder.left:
                  stacker.append(noder.left)
         return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

94. 二叉树的中序遍历 - 力扣（LeetCode） (leetcode-cn.com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        #左中右  #迭代法
        #加入一个指针用来cur
        cur = root
        stacker =[]
        res= []
        while stacker or cur:
            if cur:  #一直寻找左
              stacker.append(cur)  #并将左，从上到下储存起来
              cur= cur.left
            else:    #终了 开始将值输入到结果
               cur = stacker.pop()   #释放左 然后将左的val 给了结果 其实现在变成了中 
               res.append(cur.val)
               cur= cur.right       #然后再读取右 同样循环
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

145. 二叉树的后序遍历 - 力扣（LeetCode） (leetcode-cn.com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # 左右中  迭代
        #可以先 用中左右 即前序遍历  将左右调换 变成中右左
        #然后再取倒 即变成左右中
        if not root:return []
        stacker =[root]
        res=[]
        while stacker:
            noder= stacker.pop()
            res.append(noder.val)
            if noder.left:
                stacker.append(noder.left)
            if noder.right:
                stacker.append(noder.right)
        return res[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5.统一递归法

1)前序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        #统一的模板
        if not root: return []
        res = []
        stacker = [root]
        #前序遍历  是 中左右
        while stacker:
            noder = stacker.pop()
            if noder!= None:   #压入要倒置过来
                if noder.right:stacker.append(noder.right)
                if noder.left: stacker.append(noder.left)
                stacker.append(noder)
                stacker.append(None)
            else:
                noder = stacker.pop()
                res.append(noder.val)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2)中序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        stacker, res = [root], []
        while stacker:   
            noder = stacker.pop()
            if noder != None:  #左中右  倒置过来压入
                if noder.right: stacker.append(noder.right)
                stacker.append(noder)
                stacker.append(None)
                if noder.left: stacker.append(noder.left)
            else:
                noder = stacker.pop()
                res.append(noder.val)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3）后序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:return []
        #前中后序遍历 统一模板
        res =[]
        stacker =[root]
        while stacker:  
            noder = stacker.pop()
            if noder!= None:              #左右中
                    stacker.append(noder)                        #中
                    stacker.append(None)  #将读出标志位写入
                    if noder.right: stacker.append(noder.right)  #右
                    if noder.left: stacker.append(noder.left)    #左
            else:
                   noder= stacker.pop()
                   res.append(noder.val)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

6.总结

二叉树的东西真多… 只看了一点点,没办法,计划总共给二叉树3天的时间把