当前位置:网站首页>test about BinaryTree
test about BinaryTree
2022-07-06 18:54:00 【Frank. Ren】
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
if (root == null || node == null) {
return false;
}
stack.push(root);
if (root == node) {
return true;
}
boolean key = getPath(root.left, node, stack);
if (key) {
return true;
}
key = getPath(root.right, node, stack);
if (key) {
return true;
}
stack.pop();
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Stack<TreeNode> stack1 = new Stack<>();
getPath(root, p, stack1);
Stack<TreeNode> stack2 = new Stack<>();
getPath(root, q, stack2);
int diff = stack1.size() - stack2.size();
while (diff > 0) {
diff--;
stack1.pop();
}
while (diff < 0) {
diff++;
stack2.pop();
}
while (stack1.size() > 0) {
TreeNode cur = stack1.pop();
if (Objects.equals(cur, stack2.pop())) {
return cur;
}
}
return null;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (root == p || root == q) {
return root;
}
TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
if (leftNode != null && rightNode != null) {
return root;
} else if (leftNode != null) {
return leftNode;
} else if (rightNode != null) {
return rightNode;
}
return null;
}
}
边栏推荐
- Unity资源顺序加载的一个方法
- C#/VB.NET 给PDF文档添加文本/图像水印
- Specify flume introduction, installation and configuration
- Reproduce ThinkPHP 2 X Arbitrary Code Execution Vulnerability
- Qlabel marquee text display
- Atcoder a mountaineer
- 三年Android开发,2022疫情期间八家大厂的Android面试经历和真题整理
- Cocos2d Lua smaller and smaller sample memory game
- 上海部分招工市場對新冠陽性康複者拒絕招錄
- Splay
猜你喜欢
MySQL查询请求的执行过程——底层原理
Optical blood pressure estimation based on PPG and FFT neural network [translation]
This article discusses the memory layout of objects in the JVM, as well as the principle and application of memory alignment and compression pointer
Self-supervised Heterogeneous Graph Neural Network with Co-contrastive Learning 论文阅读
Mathematics in machine learning -- common probability distribution (XIII): Logistic Distribution
AUTOCAD——中心线绘制、CAD默认线宽是多少?可以修改吗?
[matlab] Simulink the input and output variables of the same module cannot have the same name
视频化全链路智能上云?一文详解什么是阿里云视频云「智能媒体生产」
wx小程序学习笔记day01
Introduction to the use of SAP Fiori application index tool and SAP Fiori tools
随机推荐
Jushan database was among the first batch of financial information innovation solutions!
关于npm install 报错问题 error 1
Unlock 2 live broadcast themes in advance! Today, I will teach you how to complete software package integration Issues 29-30
[sword finger offer] 60 Points of N dice
十、进程管理
2022-2024年CIFAR Azrieli全球学者名单公布,18位青年学者加入6个研究项目
From 2022 to 2024, the list of cifar azrieli global scholars was announced, and 18 young scholars joined 6 research projects
Markdown syntax for document editing (typera)
人体骨骼点检测:自顶向下(部分理论)
安装及管理程序
There is a sound prompt when inserting a USB flash disk under win10 system, but the drive letter is not displayed
Master Xuan joined hands with sunflower to remotely control enabling cloud rendering and GPU computing services
Online notes
On AAE
Penetration test information collection - CDN bypass
Atcoder a mountaineer
Numerical analysis: least squares and ridge regression (pytoch Implementation)
SQL injection Foundation
[the 300th weekly match of leetcode]
44 colleges and universities were selected! Publicity of distributed intelligent computing project list