代码随想录算法训练营day12|144.二叉树的前序遍历 94.二叉树的中序遍历 145.二叉树的后序遍历还有十道题明早刷

tristan241001 / 2024-10-11 / 原文

学习资料：https://programmercarl.com/二叉树理论基础.html

二叉树：满二叉树、完全二叉树、二叉搜索数、平衡二叉搜索树；
链式存储、顺序存储；
前序/中序/后序遍历
递归法、迭代法，层序
深度优先搜索dfs，广度优先搜索

学习记录：
144.二叉树的前序遍历（也要注重二叉数的输入方式；递归法比迭代法好理解）

点击查看代码

# 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):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # 迭代法
        result = []
        stack = []
        if root:
            stack.append(root)
        while stack:
            node = stack.pop()
            if node != None:
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
                stack.append(node)
                stack.append(None)
            else:
                node = stack.pop()
                result.append(node.val)
        return result




        # 递归法
        # res = []

        # def dfs(node):
        #     """
        #     深度优先搜索，前序遍历，根左右
        #     """
        #     if node is None:
        #         return 
        #     res.append(node.val)    # 根左右
        #     # 递归
        #     dfs(node.left) 
        #     dfs(node.right)
        
        # dfs(root)
        # return res

94.二叉树的中序遍历

点击查看代码

# 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 inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        
        def dfs(node):
            if node is None:
                return
            # 左根右
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
        
        dfs(root)
        return result

145.二叉树的后序遍历

点击查看代码

# 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 postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []

        def dfs(node):
            if node is None:   # 判断节点是否为NULL，如果是就下一条遍历了
                return
            dfs(node.left)      # 左右根
            dfs(node.right)
            result.append(node.val)
        
        dfs(root)
        return result

PS: 层序的十道题明天来完成，坐久了腰痛
阴转小雨，今晚吃了石锅拌饭，明白了人少有人少的道理，有点浪费原材料，不过还是吃的很开森，这不，又有力气干三道题了