导语:
链表与二叉树都是非常基础且非常重要的数据结构,这类题目在找工作面试中是非常高频的考题,非常考验基本功。作者在曾经在面试过程中,被要求现场写过的两道题目,分别是关于二叉树和链表的,因此对这两道题目记忆比较深刻。所以写下这篇博客与读者分享。
一.二叉树--求祖父节点值为偶数的节点和
LeetCode题目链接:力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题目描述:
给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
如果不存在祖父节点值为偶数的节点，那么返回 0 。
示例:
输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] 输出：18 解释：图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。
思路分析:
作者第一次看到此题的思路是采用递归的方法,深度优先遍历二叉树,取偶数的节点,将其孙子节点的值进行累加,代码如下:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
sum1 = 0 # 用于存储累加的结果
def sumEvenGrandparent(self, root: TreeNode):
if root is None:
return 0
if root.val % 2 == 0: # 如果当前节点的值为偶数，则遍历其孙子节点，并将子节点的值累加到sum1中
a = root.left
b = root.right
self.addchild(a)
self.addchild(b)
# 递归调用，对左子树和右子树进行遍历
self.sumEvenGrandparent(root.left)
self.sumEvenGrandparent(root.right)
return self.sum1
def addchild(self, a):
if a is not None:
if a.left is not None:
self.sum1 += a.left.val # 将左孙子节点的值累加到sum1中
if a.right is not None:
self.sum1 += a.right.val # 将右孙子节点的值累加到sum1中可以看到代码容易理解,但是代码较长,执行时间偏长:
随后作者参考别人的答案,定义一个接收三个参数的函数,三个参数分别是祖父节点,父节点和本节点,这样可以使代码简化很多,代码如下:
class Solution:
def sumEvenGrandparent(self, root: TreeNode) -> int:
# 初始化一个变量来保存偶数祖父节点的值之和
sum1 = 0
# 定义一个深度优先搜索函数，用于遍历树节点
def dfs(gr_val, p_val, node):
if node is None: # 如果节点为空，直接返回
return
if gr_val % 2 == 0: # 判断祖父节点的值是否为偶数
nonlocal sum1 # 使用nonlocal关键字声明在外部作用域中的sum1变量
sum1 += node.val # 累加当前节点的值到sum1
# 递归调用，将当前节点的值作为父节点的值，左孩子和右孩子作为当前节点继续递归
dfs(p_val, node.val, node.left)
dfs(p_val, node.val, node.right)
# 调用深度优先搜索函数，初始的祖父节点和父节点的值都为1，从根节点开始遍历
dfs(1, 1, root)
# 返回偶数祖父节点值之和
return sum1可以看到代码长度减少了,执行速度也稍微变快了点 ,两次代码的时间复杂度都为O(n)
二.链表--两数相加
LeetCode题目链接:力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题目描述:
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
思路分析:
因为本题涉及到个位数的相加问题和进位问题,所以要定义个位数num_0和十位数num_10,又由于列表的遍历需要设置一个一直在动的指针,所以需要同时创建一个不动的定指针dum,用于返回链表的头节点。然后就可以遍历l1和l2两个链表,直到两个链表都为空,且十位数为空的情况下才结束,遍历过程中通过对10取余和对10整除来获得个位数和十位数,并将个位数存入新链表的当前节点处,十位数作为进位放到下一次两值相加的适合用,最后返回链表的头节点即可。代码如下:
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 初始化两个变量用于存储当前位的数字和进位
num_0 = 0
num_10 = 0
# 创建一个哑结点，并将 cur 指针指向哑结点
cur = dum = ListNode()
# 遍历两个链表，直到两个链表和进位都为0时结束
while l1 or l2 or num_10:
# 如果 l1 为空，则将当前节点的值设为 0
if l1 is None:
l1 = ListNode(0)
# 如果 l2 为空，则将当前节点的值设为 0
if l2 is None:
l2 = ListNode(0)
# 计算当前位上的数字和进位的和，并取余得到当前位的值
num_0 = (l1.val + l2.val + num_10) % 10
# 计算进位值
num_10 = (l1.val + l2.val + num_10) // 10
# 创建新的节点，并将当前位的值赋给它
cur.next = ListNode(num_0)
# 移动 l1 和 l2 到它们的下一个节点
l1 = l1.next
l2 = l2.next
# 移动 cur 到下一个节点
cur = cur.next
# 返回哑结点的下一个节点，即为相加后的链表头节点
return dum.next可以看到执行时间还是挺快的,代码的简洁性也比较高。 代码的时间复杂度为 O(max(m, n))
三.总结
上述两题皆为作者在面试时遇到的真题,面试官要求现场手写,现场环境非常紧张,没有太多时间思考,需要完全掌握才能写的出来。链表和二叉树都是比较重要且基础的数据结构,面试的过程中出题概率基本上百分之百。
其中链表的核心遍历语句是cur=cur.next,而二叉树的遍历则分为深度优先遍历DFS和广度优先遍历BFS,深度遍历利用递归的思想,广度遍历则是采用队列的思想,python里有一个数据结构queue=collections.deque([root]),因其进出队列效率较高,通常用于遍历二叉树。在广度优先遍历时,为了操作层数,通常会对队列的长度进行操作:for _ in range(len(queue)),这样可以保证队列中的该层元素弹出完毕再开始下一层元素的弹出操作。文章来源：https://www.toymoban.com/news/detail-786948.html
总之同学们需要在掌握遍历链表和二叉树的基础上, 深入理解链表和二叉树的原理。文章来源地址https://www.toymoban.com/news/detail-786948.html
到了这里，关于面试回忆录:链表&&二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
