当前位置: 首页 > article >正文

【leetcode练习·二叉树】用「遍历」思维解题 I

本文参考labuladong算法笔记[【强化练习】用「遍历」思维解题 I | labuladong 的算法笔记]

257. 二叉树的所有路径 | 力扣 | LeetCode |

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1:

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

示例 2:

输入:root = [1]
输出:["1"]

提示:

  • 树中节点的数目在范围 [1, 100] 内
  • -100 <= Node.val <= 100

前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「遍历」的思维。

你让我求所有根节点到叶子节点的路径,那我遍历一遍二叉树肯定可以搞定,遍历到叶子节点的时候想办法把路径生成出来就行了。

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        # 遍历一遍二叉树就能出结果了
        self.traverse(root)
        return self.res

    def __init__(self):
        # 记录 traverse 函数递归时的路径
        self.path = []
        # 记录所有从根节点到叶子节点的路径
        self.res = []

    def traverse(self, root: TreeNode):
        if root is None:
            return
        # root 是叶子节点
        if root.left is None and root.right is None:
            self.path.append(str(root.val))
            # 将这条路径装入 res
            self.res.append("->".join(self.path))
            self.path.pop()
            return
        # 前序遍历位置
        self.path.append(str(root.val))
        # 递归遍历左右子树
        self.traverse(root.left)
        self.traverse(root.right)
        # 后序遍历位置
        self.path.pop()

129. 求根节点到叶节点数字之和 | 力扣 | LeetCode |

给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字:

  • 例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1:

输入:root = [1,2,3]
输出:25
解释:
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此,数字总和 = 12 + 13 = 25

示例 2:

输入:root = [4,9,0,5,1]
输出:1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此,数字总和 = 495 + 491 + 40 = 1026

提示:

  • 树中节点的数目在范围 [1, 1000] 内
  • 0 <= Node.val <= 9
  • 树的深度不超过 10
class Solution:
    def __init__(self):
        self.path = ""
        self.res = 0

    def sumNumbers(self, root: TreeNode) -> int:
        # 遍历一遍二叉树就能出结果
        self.traverse(root)
        return self.res

    # 二叉树遍历函数
    def traverse(self, root):
        if root is None:
            return
        # 前序遍历位置,记录节点值
        self.path += str(root.val)
        if root.left is None and root.right is None:
            # 到达叶子节点,累加路径和
            self.res += int(self.path)
        # 二叉树递归框架,遍历左右子树
        self.traverse(root.left)
        self.traverse(root.right)

        # 后续遍历位置,撤销节点值
        self.path = self.path[:-1]

199. 二叉树的右视图 | 力扣 | LeetCode |

给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100

from collections import deque

class Solution:
    # BFS 层序遍历解法
    def rightSideView(self, root) -> list:
        res = []
        if root is None:
            return res
        # BFS 层序遍历,计算右侧视图
        q = deque([root])
        # while 循环控制从上向下一层层遍历
        while q:
            sz = len(q)
            # 每一层头部就是最右侧的元素
            last = q[0]
            for i in range(sz):
                cur = q.popleft()
                # 控制每一层从右向左遍历
                if cur.right:
                    q.append(cur.right)
                if cur.left:
                    q.append(cur.left)
            # 每一层的最后一个节点就是二叉树的右侧视图
            res.append(last.val)
        return res

    # DFS 递归遍历解法
    def rightSideView_DFS(self, root) -> list:
        self.res = []
        # 记录递归的层数
        self.depth = 0
        self.traverse(root)
        return self.res

    # 二叉树遍历函数
    def traverse(self, root):
        if root is None:
            return
        # 前序遍历位置
        self.depth += 1
        if len(self.res) < self.depth:
            # 这一层还没有记录值
            # 说明 root 就是右侧视图的第一个节点
            self.res.append(root.val)
        # 注意,这里反过来,先遍历右子树再遍历左子树
        # 这样首先遍历的一定是右侧节点
        self.traverse(root.right)
        self.traverse(root.left)
        # 后序遍历位置
        self.depth -= 1

298. 二叉树最长连续序列 | 力扣 | LeetCode |

给你一棵指定的二叉树的根节点 root ,请你计算其中 最长连续序列路径 的长度。

最长连续序列路径 是依次递增 1 的路径。该路径,可以是从某个初始节点到树中任意节点,通过「父 - 子」关系连接而产生的任意路径。且必须从父节点到子节点,反过来是不可以的。

示例 1:

输入:root = [1,null,3,2,4,null,null,null,5]
输出:3
解释:当中,最长连续序列是 3-4-5 ,所以返回结果为 3 。

示例 2:

输入:root = [2,null,3,2,null,1]
输出:2
解释:当中,最长连续序列是 2-3 。注意,不是 3-2-1,所以返回 2 。

提示:

  • 树中节点的数目在范围 [1, 3 * 104] 内
  • -3 * 104 <= Node.val <= 3 * 104
class Solution:
    def __init__(self):
        self.maxLen = 0

    def longestConsecutive(self, root: TreeNode) -> int:
        self.traverse(root, 1, float('-inf'))
        return self.maxLen

    # 遍历二叉树,根据父节点的值判断连续的序列长度
    def traverse(self, root: TreeNode, len: int, parentVal: int):
        if root is None:
            return
        if parentVal + 1 == root.val:
            len += 1
        else:
            len = 1
        # 更新最长连续序列的长度
        self.maxLen = max(self.maxLen, len)
        # 遍历框架
        self.traverse(root.left, len, root.val)
        self.traverse(root.right, len, root.val)

988. 从叶结点开始的最小字符串 | 力扣 | LeetCode |

给定一颗根结点为 root 的二叉树,树中的每一个结点都有一个 [0, 25] 范围内的值,分别代表字母 'a' 到 'z'

返回 按字典序最小 的字符串,该字符串从这棵树的一个叶结点开始,到根结点结束

字符串中任何较短的前缀在 字典序上 都是 较小 的:

  • 例如,在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。 

节点的叶节点是没有子节点的节点。

示例 1:

输入:root = [0,1,2,3,4,3,4]
输出:"dba"

示例 2:

输入:root = [25,1,3,1,3,0,2]
输出:"adz"

示例 3:

输入:root = [2,2,1,null,1,0,null,0]
输出:"abc"

提示:

  • 给定树的结点数在 [1, 8500] 范围内
  • 0 <= Node.val <= 25

前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「遍历」的思维。

代码看起来虽然多,但思路非常简单:用 path 维护递归遍历的路径,到达叶子节点的时候判断字典序最小的路径。

不要忘了在叶子节点的时候也要正确维护 path 变量,而且要把 StringBuilder 中的字符串反转才是题目想要的答案。

class Solution:
    def smallestFromLeaf(self, root: TreeNode) -> str:
        self.traverse(root)
        return self.res
    
    # 遍历过程中的路径
    path = ""
    res = None

    # 二叉树遍历函数
    def traverse(self, root):
        if root is None:
            return
        if root.left is None and root.right is None:
            # 找到叶子结点,比较字典序最小的路径
            # 结果字符串是从叶子向根,所以需要反转
            self.path = chr(ord('a') + root.val) + self.path

            s = self.path
            if self.res is None or self.res > s:
                # 如果字典序更小,则更新 res
                self.res = s

            # 恢复,正确维护 path 中的元素
            self.path = self.path[1:]
            return
        # 前序位置
        self.path = chr(ord('a') + root.val) + self.path

        self.traverse(root.left)
        self.traverse(root.right)

        # 后序位置
        self.path = self.path[1:]

1022. 从根到叶的二进制数之和 | 力扣 | LeetCode |

前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「遍历」的思维。

用 path 变量维护每一条从根节点到叶子节点的路径形成的二进制数,到了叶子节点之后将这条路径的二进制数累加到 res 中即可。

class Solution:
    def sumRootToLeaf(self, root: TreeNode) -> int:
        self.path = 0
        self.res = 0
        self.traverse(root)
        return self.res

    def traverse(self, root: TreeNode):
        if root is None:
            return
        if root.left is None and root.right is None:
            # 叶子节点
            self.res += self.path << 1 | root.val
            return
        # 前序位置
        self.path = self.path << 1 | root.val
        self.traverse(root.left)
        self.traverse(root.right)
        # 后序位置
        self.path = self.path >> 1

1457. 二叉树中的伪回文路径 | 力扣 | LeetCode |

前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「遍历」的思维。

遍历一遍二叉树就能得到每条路径上的数字,但这题的考点在于,如何判断一组数字是否存在一个回文串组合?

稍加思考不难想到:如果一组数字中,只有最多一个数字出现的次数为奇数,剩余数字的出现次数均为偶数,那么这组数字可以组成一个回文串

题目说了 1 <= root.val <= 9,所以我们可以用一个大小为 10 的 count 数组做计数器来记录每条路径上的元素出现次数,到达叶子节点之后根据元素出现的次数判断是否可以构成回文串。

当然,我们也可以用更巧妙的位运算来实现上述逻辑:

1、首先用到异或运算的特性,1 ^ 1 = 0, 0 ^ 0 = 0, 1 ^ 0 = 1。

2、其次用到 n & (n - 1) 去除二进制最后一个 1 的技巧,详见 东哥教你几招常用的位运算技巧。

我同时实现了这两种方法,供你参考。


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.count = [0] * 10
        self.res = 0

    def pseudoPalindromicPaths(self, root: TreeNode) -> int:
        self.traverse(root)
        return self.res

    # 二叉树遍历函数
    def traverse(self, root: TreeNode):
        if root is None:
            return
        if root.left is None and root.right is None:
            # 遇到叶子节点,判断路径是否是伪回文串
            self.count[root.val] += 1
            # 如果路径上出现奇数次的数字个数大于 1,
            # 则不可能组成回文串,反之则可以组成回文串
            odd = 0
            for n in self.count:
                if n % 2 == 1:
                    odd += 1
            if odd <= 1:
                self.res += 1
            self.count[root.val] -= 1
            return

        self.count[root.val] += 1
        # 二叉树遍历框架
        self.traverse(root.left)
        self.traverse(root.right)

        self.count[root.val] -= 1

# 用位运算代替数组计数,进一步提升效率
class Solution2:
    def __init__(self):
        self.count = 0
        self.res = 0

    def pseudoPalindromicPaths(self, root: TreeNode) -> int:
        self.traverse(root)
        return self.res

    # 二叉树遍历函数
    def traverse(self, root: TreeNode):
        if root is None:
            return
        if root.left is None and root.right is None:
            # 遇到叶子节点,判断路径是否是伪回文串
            self.count ^= (1 << root.val)
            # 判断二进制中只有一位 1,原理见 https://labuladong.online/algo/frequency-interview/bitwise-operation/
            if (self.count & (self.count - 1)) == 0:
                self.res += 1
            self.count ^= (1 << root.val)
            return
        self.count ^= (1 << root.val)
        # 二叉树遍历框架
        self.traverse(root.left)
        self.traverse(root.right)

        self.count ^= (1 << root.val)

1740. 找到二叉树中的距离 | 力扣 | LeetCode |

给定一棵二叉树的根节点 root 以及两个整数 p 和 q ,返回该二叉树中值为 p 的结点与值为 q 的结点间的 距离 

两个结点间的 距离 就是从一个结点到另一个结点的路径上边的数目。

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 0
输出:3
解释:在 5 和 0 之间有 3 条边:5-3-1-0

示例 2:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 7
输出:2
解释:在 5 和 7 之间有 2 条边:5-2-7

示例 3:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 5
输出:0
解释:一个结点与它本身之间的距离为 0

提示:

  • 树中结点个数的范围在 [1, 104].
  • 0 <= Node.val <= 109
  • 树中所有结点的值都是唯一的.
  • p 和q 是树中结点的值.

这道题很明显是最近公共祖先问题(LCA)的拓展,原版的 LCA 问题是让我们返回最近公共祖先节点,现在相当于是在问 p 和 q 到最近公共祖先的树枝的距离之和。

不过说实话,这题的难度还是比较大的,需要你认真阅读我写的 一文秒杀所有二叉树最近公共祖先问题,理解 LCA 问题解法逐步演进的原理,然后再来看这道题。

具体看代码注释吧,最好结合 二叉树心法(纲领篇) 体悟一下二叉树的遍历顺序,毕竟递归算法不是线性执行的,只要搞明白代码的执行顺序就可以更深刻地理解递归。

class Solution:
    def findDistance(self, root: TreeNode, p: int, q: int) -> int:
        self.lca(root, p, q)
        return self.res

    found = False
    res = 0

    # 定义:当子树中不包含 p 或 q 时,返回 0;
    # 当子树中仅包含 p 或 q 中的一个时,返回 root 到 p 或 q 的距离;
    # 当子树中同时包含 p 和 q 时,返回一个无意义的值(答案会被存在外部变量 res 中)
    def lca(self, root: TreeNode, p: int, q: int) -> int:
        if self.found:
            # found 为 true 时答案已经被记录在全局 res 中
            # 递归函数的返回值已不需要了,此时返回什么值都无所谓
            return 123
        if root is None:
            return 0

        left = self.lca(root.left, p, q)
        right = self.lca(root.right, p, q)

        if left == 0 and right == 0:
            # root 的左右子树都不包含 p 或 q
            if root.val == p or root.val == q:
                return 1
            return 0

        if left != 0 and right != 0 and not self.found:
            # 当前节点 root 就是 p, q 的最近公共祖先节点
            # 答案已经算出来了,更新全局变量
            self.res = left + right
            # 这个递归函数的返回值已经不重要了,让它终止递归
            self.found = True
            return 456

        # 此时 left 和 right 有一个为 0,即只找到了一个节点
        # branch 就是到该节点的距离
        branch = right if left == 0 else left

        if root.val == p or root.val == q:
            self.res = branch

        return branch + 1

1257. 最小公共区域 | 力扣 | LeetCode |

给你一些区域列表 regions ,每个列表的第一个区域都包含这个列表内所有其他区域。

很自然地,如果区域 X 包含区域 Y ,那么区域 X  比区域 Y 大。

给定两个区域 region1 和 region2 ,找到同时包含这两个区域的 最小 区域。

如果区域列表中 r1 包含 r2 和 r3 ,那么数据保证 r2 不会包含 r3 。

数据同样保证最小公共区域一定存在。

示例 1:

输入:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
输出:"North America"

提示:

  • 2 <= regions.length <= 10^4
  • region1 != region2
  • 所有字符串只包含英文字母和空格,且最多只有 20 个字母。

这道题有意思,很显然是一个多叉树最近公共祖先的问题。建议看下这篇文章 二叉树最近公共祖先 中讲到的 1650. 二叉树的最近公共祖先 III。

我们可以用题目输入的 regions 结合哈希表构建多叉树,且节点指向关系是从子节点指向父节点,方便我们根据 region1, region2 回溯最近的公共祖先。构建出来之后可以直接套用 1650 的解题思路,利用 单链表的双指针技巧汇总 中讲的寻找单链表交点的算法找到答案。

# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译。
# 本代码的正确性已通过力扣验证,但可能缺失注释。必要时请对照我的 java 代码查看。

class Solution:
    def __init__(self):
        self.tree = {}

    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
        # 构建反向链接的多叉树,key 为子节点,value 为父节点
        for list in regions:
            parent = list[0]
            for child in list[1:]:
                self.tree[child] = parent

        # 转化为 1650. 二叉树的最近公共祖先 III 的解法
        return self.lowestCommonAncestor(region1, region2)

    def lowestCommonAncestor(self, p: str, q: str) -> str:
        # 施展链表双指针技巧
        a, b = p, q
        while a != b:
            # a 走一步,如果走到根节点,转到 q 节点
            a = self.tree.get(a, q)
            # b 走一步,如果走到根节点,转到 p 节点
            b = self.tree.get(b, p)
        return a

http://www.kler.cn/a/318037.html

相关文章:

  • fastadmin多个表crud连表操作步骤
  • React中 修改 html字符串 中某些元素的属性
  • goframe开发一个企业网站 验证码17
  • 批量重命名Excel文件并排序
  • zabbix搭建钉钉告警流程
  • Bugku CTF_Web——点login咋没反应
  • Flutter为Android添加签名并打包
  • 数值计算 --- 平方根倒数快速算法(上)
  • 虚拟机与物理机的文件共享
  • 【LLM学习之路】9月23日24日 第十、十一天 Attention代码解读
  • 将硬盘的GPT 转化为MBR格式
  • 如何完成等保的建设整改
  • Apache Doris 实践
  • MySQL的数据库课程设计的基本步骤和考虑因素
  • 大小端字节序 和 内存高低地址顺序
  • 3. 函数
  • MySQL误删数据怎么办?
  • 828华为云征文 | 云服务器Flexus X实例,Docker集成搭建搭建Flink
  • cpp中的namespace详解
  • 基于机器学习的癌症数据分析与预测系统实现,有三种算法,bootstrap前端+flask
  • Cubieboard2(三) 系统构建 —— WSL Ubuntu 中挂载 U 盘(SDCard)
  • Qt上下文菜单
  • C++从零实现Json-Rpc框架(项目介绍)
  • 基于SpringBoot+Vue+MySQL的智能物流管理系统
  • 中国电子学会202403青少年软件编程(Python)等级考试试卷(四级)真题
  • 8个高清视频素材网站,免费下载。