【LeetCode100】--- 二叉树的最近公共祖先

用户11288958

发布于 2025-01-21 12:50:03

2590

文章被收录于专栏：学习学习

题目传送门

方法一：递归

算法原理

分类讨论。利用递归。递归终止条件分三种情况第一种： root == null 返回 root 第二种 root == p 返回 root 第三种 root == q 返回 root 其实一共就上面这三种情况。接着不过是去当前节点的左边，当前节点的右边。去寻找 p 和 q 最近公共祖先的返回情况分三种第一种 ① p 或 q 就是当前节点root。直接返回 root 当前节点root == null 或者 root == p 或者 root == q 此时二叉树的最近公共祖先就是root 第二种： ② p 和 q都在当前节点的左边，那就递归去左边找。第三种： ③ p 和 q都在当前节点的右边。那就递归去右边找。第四种： ④ p 和 q 在当前节点的两边，那么当前节点就是最近公共祖先。

复杂度分析

时间复杂度：O（N方）空间复杂度：O（1）

代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree != null && rightTree != null){
            return root;
        }
        return leftTree == null ? rightTree : leftTree;
    }
}

方法二：相交链表（利用相交链表思想，利用栈求最近公共祖先）

算法原理

我们通过递归找出从根到目标节点的路径，使用栈存储这些路径。
通过对比这两条路径，找到它们的第一个共同节点，这个节点就是最低公共祖先。
这是一种 路径追踪 的方法，适用于寻找树中两个节点的最低公共祖先。

代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if(sizeP>sizeQ){
            int size = sizeP-sizeQ;
            while(size != 0){
                stackP.pop();
                size--;
            }
        }else{
             int size = sizeQ-sizeP;
            while(size != 0){
                stackQ.pop();
                size--;
            }           
        }
        while(!stackP.isEmpty() && !stackQ.isEmpty()){
            if(stackP.peek().equals(stackQ.peek())){
                return stackP.peek();

            }
            stackP.pop();
            stackQ.pop();
        }
        return null;
    }

    private 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 flg = getPath(root.left,node,stack);
        if(flg == true){
            return true;
            
        }
        boolean flg2 = getPath(root.right,node,stack);
        if(flg2 == true){
            return true;
            
        }
        stack.pop();
        return false;
    }
}