代码随想录学习Day 12

二叉树理论基础

在题目中二叉树主要分为两类：满二叉树和完全二叉树。

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。其深度为k，有2^k-1个节点。

完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。

之前用过的优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

上面的两种树都是没有数值的，而二叉搜索树是有数值的，并且二叉搜索树是有序的。

特点：

①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

③它的左、右子树也分别为二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。对平衡二叉搜索树插入或查询结点的时间复杂度都是O(logn)。

二叉树可以链式存储，也可以顺序存储。链式存储用指针，顺序存储用数组。链式存储如图：

顺序存储如图：如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

 二叉树主要有两种遍历方式：深度优先和广度优先。前者是先往深处走，走到叶子结点再回头；后者则是一层一层来遍历。深度优先遍历又能分为三种：前序、中序和后序。广度优先遍历主要就是层次遍历。

前中后，其实指的就是中间节点的遍历顺序，前中后序指的就是中间节点的位置。

前序中左右，中序左中右，后序左右中。

前中后序遍历都可以借助栈使用递归的方式来实现。广度优先遍历一般使用队列来实现。

 二叉树的定义：

class TreeNode:
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

二叉树的递归遍历

递归三要素：

1. 确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2. 确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3. 确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程

144.二叉树前序遍历

# 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: TreeNode) -> List[int]:
        if not root:  # 终止条件，当遇到空结点时返回空列表
            return []
        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)
        return  [root.val] + left +  right  # 中左右

145.二叉树后序遍历

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        left = self.postorderTraversal(root.left)
        right = self.postorderTraversal(root.right)
        return left + right + [root.val]  # 左右中

94.二叉树中序遍历

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)
        return left + [root.val] + right  # 左中右

二叉树的迭代遍历

前序遍历（迭代法）是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。这样出栈的顺序就是中左右。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        stack = [root]  # 将根结点入栈
        result = []
        while stack:
            node = stack.pop()  # 将根节点出栈，保证顺序为中左右
            # 中结点先处理
            result.append(node.val)  # 将结果添加到数组中
            # 右孩子先入栈
            if node.right:
                stack.append(node.right)  # 先入后出，所以右孩子先入栈
            # 左孩子后入栈
            if node.left:
                stack.append(node.left)
        return result

中序遍历（迭代法）是左中右，在遍历过程中先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），其处理顺序和访问顺序是不一致的。使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = []  # 不能提前将root结点加入stack中
        result = []
        cur = root
        while cur or stack:
            # 先迭代访问最底层的左子树结点
            if cur:  # 非空就入栈往左
                stack.append(cur)
                cur = cur.left		
            # 到达最左结点后处理栈顶结点    
            else:  # 空了就出栈输出并往右
                cur = stack.pop()
                result.append(cur.val)
                # 取栈顶元素右结点
                cur = cur.right	
        return result

后序遍历（迭代法）是左右中，只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了。

class Solution:
   def postorderTraversal(self, root: TreeNode) -> List[int]:
       if not root:
           return []
       stack = [root]
       result = []
       while stack:
           node = stack.pop()  # 根结点先出栈，最后反转数组时根结点就在最后
           # 中结点先处理
           result.append(node.val)  # 后序为左右中，但为了便于实现，采用中右左的实现方式
           # 左孩子先入栈
           if node.left:
               stack.append(node.left)  # 先入后出，所以左孩子先入
           # 右孩子后入栈
           if node.right:
               stack.append(node.right)
       # 将最终的数组翻转
       return result[::-1]  # 将本来中右左的顺序变为左右中

二叉树的统一迭代法

普通的迭代法无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

意思就是将要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。前序代码如下：

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st= []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right: #右
                    st.append(node.right)
                if node.left: #左
                    st.append(node.left)
                st.append(node) #中
                st.append(None)
            else:
                node = st.pop()
                result.append(node.val)
        return result

中序：

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right: #添加右节点（空节点不入栈）
                    st.append(node.right)
                
                st.append(node) #添加中节点
                st.append(None) #中节点访问过，但是还没有处理，加入空节点做为标记。
                
                if node.left: #添加左节点（空节点不入栈）
                    st.append(node.left)
            else: #只有遇到空节点的时候，才将下一个节点放进结果集
                node = st.pop() #重新取出栈中元素
                result.append(node.val) #加入到结果集
        return result

后序

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                st.append(node) #中
                st.append(None)
                
                if node.right: #右
                    st.append(node.right)
                if node.left: #左
                    st.append(node.left)
            else:
                node = st.pop()
                result.append(node.val)
        return result