我要评论https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
given the root of a binary tree, return the lowest common ancestor of its deepest leaves.
recall that:
-
the node of a binary tree is a leaf if and only if it has no children
-
the depth of the root of the tree is
0. if the depth of a node isd, the depth of each of its children isd + 1. -
the lowest common ancestor of a set
sof nodes, is the nodeawith the largest depth such that every node insis in the subtree with roota.
note: this question is the same as 865: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
example 1:
input: root = [3,5,1,6,2,0,8,null,null,7,4]
output: [2,7,4]
explanation: we return the node with value 2, colored in yellow in the diagram.
the nodes coloured in blue are the deepest leaf-nodes of the tree.
note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.
example 2:
input: root = [1]
output: [1]
explanation: the root is the deepest node in the tree, and it’s the lca of itself.
example 3:
input: root = [0,1,3,null,2]
output: [2]
explanation: the deepest leaf node in the tree is 2, the lca of one node is itself.
constraints:
-
the number of nodes in the tree will be in the range [ 1 , 1000 ] [1, 1000] [1,1000].
-
0 < = n o d e . v a l < = 1000 0 <= node.val <= 1000 0<=node.val<=1000
-
the values of the nodes in the tree are unique.
受leetcode - medium - 236. lowest common ancestor of a binary tree启发。
方法一：自己写的，用后序遍历模式
方法二：别人写的，用后序遍历模式
import com.lun.util.binarytree.treenode;
public class lowestcommonancestorofdeepestleaves {
//方法一：自己写的，用后序遍历模式
public treenode lcadeepestleaves(treenode root) {
object[] result = lcadeepestleaves(root, 0);
return result != null ? (treenode)result[0] : null;
}
private object[] lcadeepestleaves(treenode node, int depth) {
if(node == null) return null;
depth++;
object[] leftresult = lcadeepestleaves(node.left, depth);
object[] rightresult = lcadeepestleaves(node.right, depth);
if(leftresult == null && rightresult == null) {//叶子节点
return new object[] {node, depth};
}else if(leftresult != null && rightresult == null){
return leftresult;
}else if(leftresult == null && rightresult != null) {
return rightresult;
}else {
int leftdepth = (int)leftresult[1];
int rightdepth = (int)rightresult[1];
if(leftdepth > rightdepth) {
return leftresult;
}else if(leftdepth < rightdepth) {
return rightresult;
}else {
leftresult[0] = node;
return leftresult;
}
}
}
//方法二：别人写的，用后序遍历模式
public treenode lcadeepestleaves2(treenode root) {
pair p = getlca(root, 0);
return p.node;
}
private pair getlca(treenode root, int d) {
if (root == null) return new pair(null, d);
pair l = getlca(root.left, d + 1);
pair r = getlca(root.right, d + 1);
if (l.d == r.d) {
return new pair(root, l.d);
} else {
return l.d > r.d ? l : r;
}
}
private class pair {
treenode node;
int d;
pair(treenode node, int d) {
this.node = node;
this.d = d;
}
}
最后
分享一些系统的面试题，大家可以拿去刷一刷，准备面试涨薪。
这些面试题相对应的技术点：
- jvm
- mysql
- mybatis
- mongodb
- redis
- spring
- spring boot
- spring cloud
- kafka
- rabbitmq
- nginx
- …
大类就是：
- java基础
- 数据结构与算法
- 并发编程
- 数据库
- 设计模式
- 微服务
- 消息中间件
[外链图片转存中…(img-raljdppc-1718902274431)]
[外链图片转存中…(img-bhtrqiix-1718902274432)]
[外链图片转存中…(img-3if0novm-1718902274432)]
[外链图片转存中…(img-fldlne8h-1718902274433)]
[外链图片转存中…(img-rktgg8cv-1718902274434)]
[外链图片转存中…(img-bsepiems-1718902274434)]
[外链图片转存中…(img-wzip8a5a-1718902274435)]
发表评论