算法题(八)--相同的树
2021/12/26 12:07:11
本文主要是介绍算法题(八)--相同的树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
解法一、广度优先
思路:每棵树维护一个栈,栈里面用来记录没一层节点的值,如果没一层节点的值相同,则代表是结构和值都相同,如果不符合就代表不是相同的树,直接跳出循环。
代码:
# 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 isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ def find_level_vale(list_node): temp = [];temp_node = [] for item in list_node: if item != None: temp.append(item.val) temp_node.append(item.left) temp_node.append(item.right) else: temp.append("none") return temp,temp_node stack_1 = [];stack_2 = [] stack_1.append(p);stack_2.append(q) while stack_1: temp1,temp1_node = find_level_vale(stack_1) temp2,temp2_node = find_level_vale(stack_2) if temp1 != temp2: return False stack_1 = temp1_node stack_2 = temp2_node return True
解法二、深度优先
思路:维护一个栈,判断栈中每个节点的最深树结构和值是否相同,如果不同就结束判断。前序、中序、后序遍历都是深度优先算法的一种,因此可以选择一种作为实现方案。
# 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 isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if p == None and q == None: return True else: return False def inner_left(node,stack): while node.left != None: stack.append(node.left) stack1 = [];stack2 = [] stack1.append(p);stack2.append(q) inner_left(p,stack1);inner_left(q,stack2) while stack1: temp1 = stack1.pop() temp2 = stack2.pop() if temp1.val != temp2.val: return False if temp1.right != None: inner_left(temp1.right,stack1) if temp2.right != None: inner_left(temp2.right,stack2) return True
这篇关于算法题(八)--相同的树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南