【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