二叉树oj -----＞二叉树的最近公共祖先

桃扇骨 2023-10-02 15:15 17阅读 0赞

**题目内容：**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

**解题思路：**

> **公共祖先的意思就是，离这两个结点最近的公共结点，有可能是他们的双亲，也有可能是他们双亲的双亲，所以，我们的解题思路也随之而来了，就是寻找在到达他们的路径上，有没有出现重合的结点，那么这就是他们的最近的公共祖先**
> 
>  *  **给一个查找路径的方法**
>  *  **将所到的结点，按正确的存储方式放在栈当中**
>  *  **进行比较，如果有相同的，就返回他，若没有就返回null**

**解题代码：**

class Solution {
        public boolean getNode(TreeNode root,Stack<TreeNode> s,TreeNode node){
            //进行检测，判断是否为空，如果有一个为空，就直接返回
            if(root == null || node == null){
                return false;
            }
            //将结点入栈
            s.push(root);
            //如果结点刚好和node相等就直接返回
            if(root == node){
                return true;
            }
    
            //开始进行递归，如果在左子树当中就返回true
            if(getNode(root.left,s,node)){
                return true;
            }
            if(getNode(root.right,s,node)){
                return true;
            }
            //走到这里说明此时栈顶的元素不是我们要找结点所走的路径，将栈顶的元素移除掉
            s.pop();
            return false;
        }
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || p == null || q == null){
                return null;
            }
            Stack<TreeNode> s1 = new Stack<>();
            Stack<TreeNode> s2 = new Stack<>();
    
            getNode(root,s1,p);
            getNode(root,s2,q);
    
            int ps = s1.size();
            int qs = s2.size();
    
            while(!s1.empty() && !s2.empty()){
                if(s1.peek() == s2.peek()){
                    return s1.peek();
                }
    
                if(ps > qs){
                    s1.pop();
                    ps--;
                }else if(qs > ps){
                    s2.pop();
                    qs--;
                }else{
                    s1.pop();
                    s2.pop();
                    ps--;
                    qs--;
                }
            }
            return null;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/62d3a784fff94d46b91ad73d280dc597.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16