gpt4 book ai didi

java - 二叉树中最低的共同祖先。超过时间限制

转载 作者:行者123 更新时间:2023-12-02 04:00:17 26 4
gpt4 key购买 nike

我编写了这个解决方案来查找二叉树的 LCA。它给出了较大输入超出的时间限制。有人可以指出这段代码中的问题吗?此题来自Leetcode OJ。

public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}if((p.val == root.val) || (q.val == root.val)){
return root;
}
if(root.left == null && root.right == null){
return null;
}
boolean leftChildP = isLeftChild(root,p);
boolean leftChildQ = isLeftChild(root,q);

if(isRightChild(root,p) && isLeftChild(root,q)){
return root;
}if(isRightChild(root,q) && isLeftChild(root,p)){
return root;
}
if(leftChildP && leftChildQ){
return lowestCommonAncestor(root.left,p,q);
}
return lowestCommonAncestor(root.right,p,q);}


private boolean isLeftChild(TreeNode root, TreeNode node){
return isChild(root.left,node);
}


private boolean isRightChild(TreeNode root, TreeNode node){
return isChild(root.right,node);
}


private boolean isChild(TreeNode parent, TreeNode child){
if(parent == null){
return false;}
if(parent.val == child.val){
return true;
}return (isChild(parent.left,child) || isChild(parent.right,child));
}}

最佳答案

您编写的代码复杂度为 O(n^2)。

您可以通过两种方式在 O(n) 中找到 LCA

1.) 将两个节点(p 和 q)的根存储到节点路径(在 ArrayList 中或可以使用哈希集)。现在开始比较从根开始的两条路径中的节点(直到 LCA 的路径应该匹配 p 和 q),因此路径中发生不匹配时之前的节点将是 LCA。这个解决方案应该在 O(n) 内工作。

2.) 其他解决方案的工作原理是这样的:如果 p 和 q 中只有一个节点存在于树中,那么 lca 函数将返回该节点。这是您可以执行的代码

public BinaryTreeNode<Integer> lca(BinaryTreeNode<Integer> root, int data1, int data2){
if(root == null){
return null;
}
if(root.data == data1 || root.data == data2){
return root;
}
BinaryTreeNode<Integer> leftAns = lca(root.left, data1 , data2);
BinaryTreeNode<Integer> rightAns = lca(root.left, data1 , data2);
/
// If you are able to find one node in left and the other in right then root is LCA
if(leftAns!= null && rightAns != null){
return root;
}
if(leftAns!=null){
return leftAns;
}
else{
return rightAns;
}
}

时间复杂度为 O(n)

关于java - 二叉树中最低的共同祖先。超过时间限制,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35004511/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com