leetcode 872. 叶子相似的树
2023-03-14 22:52:03 时间
叶子相似的树题解汇总
DFS
- 写法1:
class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2)
{
vector<int> v1;
vector<int> v2;
dfs(root1, v1);
dfs(root2, v2);
return v1 == v2;
}
void dfs(TreeNode* root, vector<int>& v)
{
if(root==NULL) return;
//现将左子树的叶子节点加入
dfs(root->left,v);
//叶子节点,加入数组,返回
if (!root->left && !root->right)
{
v.push_back(root->val);
}
//再将右子树的节点加入
dfs(root->right, v);
}
};
- 写法2:
class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2)
{
vector<int> v1;
vector<int> v2;
dfs(root1, v1);
dfs(root2, v2);
return v1 == v2;
}
void dfs(TreeNode* root, vector<int>& v)
{
if(root==NULL) return;
//叶子节点,加入数组,返回
if (!root->left && !root->right)
{
v.push_back(root->val);
}
//现将左子树的叶子节点加入
dfs(root->left,v);
//再将右子树的节点加入
dfs(root->right, v);
}
};
- 写法3:
class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2)
{
vector<int> v1;
vector<int> v2;
dfs(root1, v1);
dfs(root2, v2);
return v1 == v2;
}
void dfs(TreeNode* root, vector<int>& v)
{
if(root==NULL) return;
//现将左子树的叶子节点加入
dfs(root->left,v);
//再将右子树的节点加入
dfs(root->right, v);
//叶子节点,加入数组,返回
if (!root->left && !root->right)
{
v.push_back(root->val);
}
}
};
- 上面三种写法对应二叉树前中后序遍历,在这里有一个共同点:都是先将左叶子放入再放入右叶子,因此这三种写法得到的结果数组都是一致的。
同步遍历
- 使用两个栈分别记录两棵树其下一次出发搜寻叶子节点的起始点.
- 只要有任意一个栈为空,说明其树以经遍历完毕。这里有两种情况:
- 两个栈都空了,并且叶子节点都相等,因此返回true
- 只有一颗树空了,证明另一棵树一定还有别的叶子节点, 因此返回false
- 分别取出两个栈中两颗树出发搜寻叶子节点的起始点,并出发找到其对于的叶子节点。左孩子不为空时,如果右孩子也不为空,则将其推入栈作为下次的起始点。然后继续往左搜寻叶子节点。
- 左孩子为空时,那么右孩子一定不为空,则出发往右孩子寻找第一个叶子节点。
- 当两棵树分别都找到叶子节点后,比较它们的值是否相等,如果不相等则返回false, 相等则继续找下一个叶子节点。
class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
stack<TreeNode*> s1, s2;
s1.push(root1), s2.push(root2);
while(!s1.empty() && !s2.empty())
{
TreeNode* node1 = s1.top(); s1.pop();
TreeNode* node2 = s2.top(); s2.pop();
//找叶子节点
while(node1->left || node1->right)
{
if(node1->left)
{
//把不为空的右子树节点压栈
if(node1->right) s1.push(node1->right);
node1 = node1->left;
}
else
node1 = node1->right;
}
//同样的操作对树2进行一遍
while(node2->left || node2->right)
{
if(node2->left)
{
if(node2->right) s2.push(node2->right);
node2 = node2->left;
}
else
node2 = node2->right;
}
//此时node1与node2分别指向树1与树2的叶子节点
if(node1->val != node2->val) return false;
}
//到此两种情况:
//1. 两个栈都空了,并且叶子节点都相等,因此返回true
//2. 只有一颗树空了,证明另一棵树一定还有别的叶子节点, 返回false;
return s1.empty() && s2.empty();
}
};
相关文章
- 如何快速构建跨多账号的云CMDB和安全基线检查方案
- JAVA Optional
- Amazon EC2 现在支持 NitroTPM 和 UEFI 安全启动
- 一键搞定云端网络环境,让您轻松迁移至AWS!
- 利用QuickSight和AWS serverless服务创建跨账号的支持案例面板
- 带你SSH到Amazon SageMaker 训练实例一探究竟
- AWS 一周回顾 — 2022 年 5 月 9 日
- 使用 Readiness Gate 解决 EKS Pod 滚动升级产生的服务中断
- 手把手教你如何用Lambda + Alexa调用echo设备
- EC2 Spot实例中断引起的AWS Batch任务重试优化
- 新增 – 存储优化型 Amazon EC2 实例 (I4i),由英特尔至强可扩展 (Ice Lake) 处理器提供支持
- 多伦多的新 AWS Wavelength 区域 – 加拿大首个
- Python---Tkinter---计算器
- AWS 一周回顾 – 2022 年 5 月 2 日
- 基于Amazon Kinesis Video Streams 与 Amazon Rekognition Streaming Video Events实时视频检测方案
- 多账号环境下的密钥管理策略决策分析
- 使用 AWS Glue、Apache Hudi 和 Amazon S3 构建无服务器管道以分析串流数据
- 使用AWS托管MSK Connector和EMR Flink从AWS RDS进行CDC数据消费
- 自动驾驶数据湖(四):可视化
- 通过Istio在Amazon EKS上实现灰度发布