GIS与Climate

V1

2022/10/05阅读:23主题:默认主题

算法60天-Day15:二叉树基础和遍历

代码随想录(截图自参考【1】)
代码随想录(截图自参考【1】)

本系列是代码随想录算法训练营的学习笔记之day15,主要记录一下刷题的过程,以及核心知识点和一些值的记录的问题。

  • 落下了几天,需要补了。。

代码随想录的资源可以看参考链接【1】。

今日知识点

二叉树基础:

  • 二叉树中的几个关键词:结点、度、叶子结点
  • 二叉树的两种主要形式包括满二叉树和完全二叉树
满二叉树(完美二叉树)
满二叉树(完美二叉树)
  • 满二叉树只有度为0和度为2的结点;
  • 在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1) 个节点。
完全二叉树
完全二叉树
  • 二叉搜索树:有序树,左子树上所有节点的值小于根结点的值,右子树上所有节点的值大于根结点的值;
二叉搜索树
二叉搜索树
  • 平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
平衡二叉搜索树
平衡二叉搜索树
  • 二叉树的储存方式:链式存储
链式存储
链式存储
顺序存储
顺序存储
  • 用数组存储的二叉树如何遍历呢?如果父节点的下标是i,则左孩子是2i+1,右孩子是2i+2;

  • 二叉树的遍历方式主要有深度优先遍历和广度优先遍历:

    • 深度优先:前序遍历、中序遍历、后序遍历;
    • 广度优先:层次遍历
  • 其他的更多理论基础可以去看参考链接【2】;

今日题目

今天的题目主要是代码实现二叉树的遍历相关操作基础。

  1. 二叉树的前序遍历(144)

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

链接:https://leetcode.cn/problems/binary-tree-preorder-traversal/

  • 递归法
# 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]:
        re = []

        def myfun(root):
            if root == None:
                return
            re.append(root.val)
            myfun(root.left)
            myfun(root.right)

        myfun(root)

        return re
  • 迭代法
# 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 []
        stack = [root]
        re = []
        while stack:
            node = stack.pop()
            re.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return re 
  1. 二叉树的中序遍历(94)

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/

  • 递归法
# 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]:
        re = []

        def traversal(root):
            if root==None:
                return 
            traversal(root.left)
            re.append(root.val)
            traversal(root.right)
        
        traversal(root)
        return re

  • 迭代法
# 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 []
        stack = []
        re = []
        cur = root
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                re.append(cur.val)
                cur = cur.right
        return re
  1. 二叉树的后序遍历(145)

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。

链接:https://leetcode.cn/problems/binary-tree-postorder-traversal/

  • 递归法
# 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]:
        re = []
        def traversal(root):
            if root==None:
                return 
            traversal(root.left)
            traversal(root.right)
            re.append(root.val)

        traversal(root)
        return re 

  • 迭代法
# 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 []
        stack = [root]
        re = []
        while stack:
            node = stack.pop()
            re.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        
        return re[::-1]

思路

  • 要牢记我们遍历的时候处理的对象一直是中间结点的值,在合适的“顺序”把结点的值保存到列表中;
  • 栈是先入后出的!所以前序遍历的时候先放右结点,再放左结点,这样子出的时候才是先左后右;
  • pop函数模拟出栈,append模拟入栈;
  • 后序遍历的顺序是左右中,可以在前序遍历的基础上变化出入栈的顺序(出栈之后的结果是中右左),然后最后的时候翻转数组;

二叉树的统一迭代法

上面的几种迭代方式不够统一,比如在前序和后序中,root一开始是入栈的,但是中序开始的时候root不入栈,不方便理解和记忆,代码随想录网站上给出了统一方式的写法,这里直接搬运下,因为今天知识量超了。。得消化消化。

  • 前序遍历
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

二叉树的知识有点多,也有点难记,还得继续努力~

前面缺的几天慢慢补。。先跟上队伍。

参考

【1】代码随想录:https://programmercarl.com/
【2】https://www.bilibili.com/video/BV1Hy4y1t7ij/?spm_id_from=333.337.search-card.all.click&vd_source=878f5382c5ebdd5fc558a620040e965f
【3】https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html#%E8%BF%AD%E4%BB%A3%E6%B3%95%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86

分类:

后端

标签:

数据结构与算法

作者介绍

GIS与Climate
V1

公众号:GIS与Climate,欢迎关注