当前位置:网站首页>test about BinaryTree
test about BinaryTree
2022-07-06 10:53: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;
}
}
边栏推荐
猜你喜欢
随机推荐
Test 1234
Celery best practices
解读云原生技术
具体说明 Flume介绍、安装和配置
2022-2024年CIFAR Azrieli全球学者名单公布,18位青年学者加入6个研究项目
SQL injection Foundation
POJ 2208 已知边四面体六个长度,计算体积
CSRF漏洞分析
Cobra quick start - designed for command line programs
Medical image segmentation
[sword finger offer] 60 Points of N dice
JDBC驱动器、C3P0、Druid和JDBCTemplate相关依赖jar包
Visual Studio Code启动时提示“Code安装似乎损坏。请重新安装。”、标题栏显示“不受支持”信息的解决办法
DOM Brief
Brief description of SQL optimization problems
Easy to use PDF to SVG program
Reproduce ThinkPHP 2 X Arbitrary Code Execution Vulnerability
Cobra 快速入门 - 专为命令行程序而生
[.Net core] solution to error reporting due to too long request length
None of the strongest kings in the monitoring industry!