当前位置:网站首页>leetcode刷题:二叉树13(相同的树)
leetcode刷题:二叉树13(相同的树)
2022-07-05 19:52:00 【涛涛英语学不进去】
100. 相同的树
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
傻瓜式方法,按p的轨迹遍历运行一遍,再按q的轨迹遍历运行一遍。
package com.programmercarl.tree;
import lombok.val;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/** * @ClassName IsSameTree * @Descriotion TODO * @Author nitaotao * @Date 2022/7/4 19:50 * @Version 1.0 **/
public class IsSameTree {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
TreeNode tempP=p;
TreeNode tempQ=q;
Stack<TreeNode> stackP = new Stack<TreeNode>();
Stack<TreeNode> stackQ = new Stack<TreeNode>();
while (p != null || !stackP.isEmpty()) {
if (p != null) {
stackP.push(p);
stackQ.push(q);
p = p.left;
if (q == null || stackP.isEmpty()) {
return false;
}
q = q.left;
} else {
p = stackP.pop();
q = stackQ.pop();
if (p.val != q.val) {
return false;
}
p = p.right;
q = q.right;
}
}
Stack<TreeNode> stackp = new Stack<TreeNode>();
Stack<TreeNode> stackq = new Stack<TreeNode>();
while (tempQ != null || !stackq.isEmpty()) {
if (tempQ != null) {
stackp.push(tempP);
stackq.push(tempQ);
tempQ= tempQ.left;
if (tempP == null || stackp.isEmpty()) {
return false;
}
tempP= tempP.left;
} else {
tempP = stackp.pop();
tempQ = stackq.pop();
if (tempP.val != tempQ.val) {
return false;
}
tempP = tempP.right;
tempQ = tempQ.right;
}
}
return true;
}
}
看看大佬的 递归+迭代
public boolean isSameTree(TreeNode p, TreeNode q) {
return compare(p, q);
}
//可以看成两个子树,左右子树
private boolean compare(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
//不是两个都为空
//其中为空
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
boolean leftResult = compare(left.left, right.left);
boolean rightResult = compare(left.right, right.right);
return leftResult && rightResult;
}
边栏推荐
- Fundamentals of shell programming (Chapter 9: loop)
- Debezium series: modify the source code to support UNIX_ timestamp() as DEFAULT value
- SecureRandom那些事|真伪随机数
- 期货如何网上开户?安不安全?
- IBM大面积辞退40岁+的员工,掌握这十个搜索技巧让你的工作效率至上提高十倍
- What do software test engineers do? How about the prospect of treatment?
- 深度學習 卷積神經網絡(CNN)基礎
- Thread pool parameters and reasonable settings
- 多分支结构
- Build your own website (16)
猜你喜欢
建议收藏,我的腾讯Android面试经历分享
安卓面试宝典,2022Android面试笔试总结
How to choose the notion productivity tools? Comparison and evaluation of notion, flowus and WOLAI
C application interface development foundation - form control (5) - grouping control
建立自己的网站(16)
[FAQ] summary of common causes and solutions of Huawei account service error 907135701
测试的核心价值到底是什么?
Django uses mysqlclient service to connect and write to the database
Android interview classic, 2022 Android interview written examination summary
Successful entry into Baidu, 35K monthly salary, 2022 Android development interview answer
随机推荐
Necessary skills for interview in large factories, 2022android will not die, I will not fall
Gstreamer中的task
Let's talk about threadlocalinsecurerandom
Is it safe for Guosen Securities to open an account online?
JVMRandom不可设置种子|问题追溯|源码追溯
MMO项目学习一:预热
Reptile exercises (II)
众昂矿业:2022年全球萤石行业市场供给现状分析
acm入门day1
40000 word Wenshuo operator new & operator delete
Redis cluster simulated message queue
安卓面试宝典,2022Android面试笔试总结
c——顺序结构
Microwave radar induction module technology, real-time intelligent detection of human existence, static micro motion and static perception
Float. The specific meaning of the return value of floattorawintbits is to convert float into byte array
Tasks in GStreamer
After 95, Alibaba P7 published the payroll: it's really fragrant to make up this
Is it safe for Guohai Securities to open an account online?
通配符选择器
多分支结构