当前位置:网站首页>Leetcode brush question: binary tree 13 (the same tree)
Leetcode brush question: binary tree 13 (the same tree)
2022-07-05 20:03:00 【Taotao can't learn English】
100. Same tree
Given two binary trees , Write a function to verify that they are the same .
If two trees are the same in structure , And the nodes have the same value , They are the same .
Fool's method , Press p Track traversal run again , Press again q Track traversal run again .
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;
}
}
Look at the boss recursive + iteration
public boolean isSameTree(TreeNode p, TreeNode q) {
return compare(p, q);
}
// It can be seen as two subtrees , Left and right subtrees
private boolean compare(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
// Not both are empty
// Where is empty
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;
}
边栏推荐
- ICTCLAS用的字Lucene4.9捆绑
- How to safely and quickly migrate from CentOS to openeuler
- How to apply smart contracts more wisely in 2022?
- sun.misc.BASE64Encoder报错解决方法[通俗易懂]
- 淺淺的談一下ThreadLocalInsecureRandom
- Fundamentals of deep learning convolutional neural network (CNN)
- 图嵌入Graph embedding学习笔记
- openh264解码数据流向分析
- leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
- . Net distributed transaction and landing solution
猜你喜欢
After 95, Alibaba P7 published the payroll: it's really fragrant to make up this
C application interface development foundation - form control (5) - grouping control
Jvmrandom cannot set seeds | problem tracing | source code tracing
【无标题】
Do you know several assertion methods commonly used by JMeter?
深度学习 卷积神经网络(CNN)基础
如何安全快速地从 Centos迁移到openEuler
Win10 x64环境下基于VS2017和cmake-gui配置使用zxing以及opencv,并实现data metrix码的简单检测
How to apply smart contracts more wisely in 2022?
What is the core value of testing?
随机推荐
《乔布斯传》英文原著重点词汇笔记(十二)【 chapter ten & eleven】
. Net distributed transaction and landing solution
Interviewer: what is the internal implementation of set data types in redis?
【无标题】
95后阿里P7晒出工资单:狠补了这个,真香...
third-party dynamic library (libcudnn.so) that Paddle depends on is not configured correctl
解决php无法将string转换为json的办法
Database logic processing function
Zero cloud new UI design
Tasks in GStreamer
Parler de threadlocal insecurerandom
leetcode刷题:二叉树15(找树左下角的值)
Force buckle 1200 Minimum absolute difference
Base du réseau neuronal de convolution d'apprentissage profond (CNN)
深度学习 卷积神经网络(CNN)基础
浮动元素与父级、兄弟盒子的关系
Securerandom things | true and false random numbers
多分支结构
- Oui. Net Distributed Transaction and Landing Solution
Is it safe for Guosen Securities to open an account online?