首页 > 其他分享 >LeetCode 刷题—树

LeetCode 刷题—树

时间:2024-09-08 17:47:30浏览次数:8  
标签:node index None LeetCode nodes root 节点 刷题

一:树

1、树描述的是一个父子关系;有节点;根节点;叶子节点三个相关的概念

2、树的高度;深度;层

3、二叉树:每个节点最多只有两个孩子

4、完全二叉树:除了叶子节点;每个孩子并不要求都为两个孩子(从上到下,从左到右依次填满节点)

5、满二叉树:除了叶子节点;每个节点都有两个孩子

6、二叉树的遍历

(1)前序遍历:根节点-->左孩子-->右孩子

(2)中序遍历:左孩子-->根节点-->右孩子

(3)后序遍历:左孩子-->右孩子-->根节点

7、树在程序设计当中;一般会直接给出树的结构;不会让你去创建一个树

二:刷题

144 后序遍历二叉树

(1)思路就是先将数组转化二二叉树;然后根据后序遍历的特性依次访问左子树;右子树;最后访问根节点

from collections import deque
# 定义二叉树节点的类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
# 迭代方法将列表转换为二叉树
def build_tree_iterative(nodes):
    if not nodes:
        return None
    root = TreeNode(nodes[0])  # 创建根节点
    queue = deque([root])  # 使用队列来追踪节点
    index = 1
    while queue and index < len(nodes):
        node = queue.popleft()  # 取出队列中的第一个节点
        # 处理左子树
        if index < len(nodes) and nodes[index] is not None:
            node.left = TreeNode(nodes[index])
            queue.append(node.left)  # 左子节点加入队列
        index += 1
        # 处理右子树
        if index < len(nodes) and nodes[index] is not None:
            node.right = TreeNode(nodes[index])
            queue.append(node.right)  # 右子节点加入队列
        index += 1
    return root
# 层序遍历打印二叉树的节点值
def print_tree_level_order(root):
    if not root:
        print("[]")
        return
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    # 去除结果列表末尾的 None
    while result and result[-1] is None:
        result.pop()
    print(result)
# 示例
nodes = [1, None, 2, 3]
root = build_tree_iterative(nodes)
print_tree_level_order(root)

前序遍历树

from collections import deque

# 定义二叉树节点的类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 迭代方法将列表转换为二叉树
def build_tree_iterative(nodes):
    if not nodes:
        return None
    root = TreeNode(nodes[0])  # 创建根节点
    queue = deque([root])  # 使用队列来追踪节点
    index = 1
    while queue and index < len(nodes):
        node = queue.popleft()  # 取出队列中的第一个节点
        # 处理左子树
        if index < len(nodes) and nodes[index] is not None:
            node.left = TreeNode(nodes[index])
            queue.append(node.left)  # 左子节点加入队列
        index += 1
        # 处理右子树
        if index < len(nodes) and nodes[index] is not None:
            node.right = TreeNode(nodes[index])
            queue.append(node.right)  # 右子节点加入队列
        index += 1
    return root

# 前序遍历打印二叉树的节点值
def print_tree_preorder(root):
    if not root:
        print("[]")
        return
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        if node:
            result.append(node.val)
            stack.append(node.right)  # 先右后左
            stack.append(node.left)  # 左子节点先入栈,确保左子树优先处理
    
    print(result)

# 示例
nodes = [1, None, 2, 3]
root = build_tree_iterative(nodes)
print_tree_preorder(root)

中序遍历二叉树

from collections import deque

# 定义二叉树节点的类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 迭代方法将列表转换为二叉树
def build_tree_iterative(nodes):
    if not nodes:
        return None
    root = TreeNode(nodes[0])  # 创建根节点
    queue = deque([root])  # 使用队列来追踪节点
    index = 1
    while queue and index < len(nodes):
        node = queue.popleft()  # 取出队列中的第一个节点
        # 处理左子树
        if index < len(nodes) and nodes[index] is not None:
            node.left = TreeNode(nodes[index])
            queue.append(node.left)  # 左子节点加入队列
        index += 1
        # 处理右子树
        if index < len(nodes) and nodes[index] is not None:
            node.right = TreeNode(nodes[index])
            queue.append(node.right)  # 右子节点加入队列
        index += 1
    return root

# 中序遍历打印二叉树的节点值
def print_tree_inorder(root):
    if not root:
        print("[]")
        return
    
    result = []
    stack = []
    current = root
    
    while stack or current:
        # 遍历左子树
        while current:
            stack.append(current)
            current = current.left
        
        # 处理当前节点
        current = stack.pop()
        result.append(current.val)
        
        # 遍历右子树
        current = current.right
    
    print(result)

# 示例
nodes = [1, None, 2, 3]
root = build_tree_iterative(nodes)
print_tree_inorder(root)

标签:node,index,None,LeetCode,nodes,root,节点,刷题
From: https://www.cnblogs.com/gsupl/p/18403174

相关文章

  • LeetCode //C - 350. Intersection of Two Arrays II
    350.IntersectionofTwoArraysIIGiventwointegerarraysnums1andnums2,returnanarrayoftheirintersection.Eachelementintheresultmustappearasmanytimesasitshowsinbotharraysandyoumayreturntheresultinanyorder. Example1:......
  • Leetcode第 414 场周赛题解
    Leetcode第414场周赛题解Q1.将日期转换为二进制表示给你一个字符串date,它的格式为yyyy-mm-dd,表示一个公历日期。date可以重写为二进制表示,只需要将年、月、日分别转换为对应的二进制表示(不带前导零)并遵循year-month-day的格式。返回date的二进制表示。解法:STL一......
  • Leetcode面试经典150题-76.最小覆盖子串
    解法都在代码里,不懂就留言或者私信理论上提交这个就是最优解classSolution{publicStringminWindow(Strings,Stringt){if(s.length()<t.length()){return"";}/**转成字符数组*/char[]sArr=s.toCharArr......
  • 代码随想录算法训练营第九天 | Javascript | 力扣Leetcode | 手撕KMP的一天 | 28. 找
    目录前言简介题目链接:28.找出字符串中第一个匹配项的下标题目链接:459.重复的子字符串前言踏平坎坷成大道,斗罢艰险又出发!自律的尽头是自控,自控的尽头是硬控。愿道友们披荆斩棘,终能得偿所愿。简介本人是小几年经验的前端开发,算法基础只有力扣几十道题,非常薄弱。......
  • 392. 判断子序列(leetcode)
    https://leetcode.cn/problems/is-subsequence/description/classSolution{publicbooleanisSubsequence(Strings,Stringt){//依据题意,可以判断是求最长公共子序列的特殊情况//f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+1)//f[1]......
  • LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现N*K时间复杂度
    3177.求出最长好子序列II题目链接题目描述给你一个整数数组nums和一个非负整数k。如果一个整数序列seq满足在下标范围[0,seq.length-2]中最多只有k个下标i满足seq[i]!=seq[i+1],那么我们称这个整数序列为好序列。请你返回nums中好子序列的最长长度......
  • Leetcode 第 409 场周赛题解
    Leetcode第409场周赛题解Leetcode第409场周赛题解题目1:3242.设计相邻元素求和服务思路代码复杂度分析题目2:3243.新增道路查询后的最短距离I思路代码复杂度分析题目3:3244.新增道路查询后的最短距离II思路代码复杂度分析题目4:3245.交替组III思路代码复杂度......
  • LCP 485. 最大连续 1 的个数[lleetcode -11]
    从今天起,我们的算法开始研究搜索,首先就是DFS深度优先搜索(depth-firstseach,DFS)在搜索到一个新的节点时,立即对该新节点进行遍历;因此遍历需要用先入后出的栈来实现,也可以通过与栈等价的递归来实现。对于树结构而言,由于总是对新节点调用遍历,因此看起来是向着“深”的方向前进......
  • Leetcode 029 两数相除
    给你两个整数,被除数dividend和除数divisor。将两数相除,要求不使用乘法、除法和取余运算。整数除法应该向零截断,也就是截去(truncate)其小数部分。例如,8.345将被截断为8,-2.7335将被截断至-2。返回被除数dividend除以除数divisor得到的商。注意:假设我们的环境只能......
  • 【Golang】LeetCode面试经典150题:45. 跳跃游戏 II
    题干:给定一个长度为 n 的 0索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i+j] 处:0<=j<=nums[i] i+j<n返回到达 nums[n-1] 的最小跳跃次数......