java寻找二叉树的两个结点的最近公共祖先

傷城~ 2024-03-16 11:08 34阅读 0赞

## 二叉树的最近公共祖先 ##

### 问题描述 ###

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。  
百度百科中最近公共祖先的定义为：

> “对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x的深度尽可能大（一个节点也可以是它自己的祖先）。”

### 示例 ###

![在这里插入图片描述][34d396e926064f7f8311f69d999ed8ca.png]![在这里插入图片描述][b26df8dcbd3540a0bea470b6bf30ccea.png]![在这里插入图片描述][415df088f92d42189c631d67617f3ea8.png]

### 原题OJ链接 ###

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/submissions/

### 解答代码 ###

#### 方法一 ####

/**
     * 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){
        //p,q其中一个是根节点，那么祖先就是根节点
            //这一行代码也是用来递归寻找p,q结点的   3
                return root;
            }
            //往左子树去找p，q结点
            TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
            //往右子树去找p，q结点
            TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
    
            if(leftRet != null && rightRet != null){
         
                return root;//说明pq分布分布在root的左右两边，那么他们的公共结点一定是root结点  1
            }
            else if(leftRet != null){
        
                return leftRet;//说明pq都分布在根节点左边，那么一直往下找，无论pq谁先被找到谁就是祖先结点   2
            }
            else if(rightRet != null){
        
                return rightRet;//说明pq都分布在根节点右边边，那么一直往下找，无论pq谁先被找到谁就是祖先结点
            }
            //最后一种情况，就是qp根本没有公共祖先
            return null;      
        }
    }

如下图就是上述代码 **1** 的情况  
![在这里插入图片描述][21cc63add59b43aead484467193fec88.png]

如下图就是上述代码 **2** 的情况

![在这里插入图片描述][30cab77e6cbd4c568be069edc910185f.png]如下图就是上述代码 **3** 的情况  
![在这里插入图片描述][287edadb7e494d3a9a504bf433056e58.png]

#### 方法二 ####

此外还可以先将根节点到q,p结点的路径寻找到，然后用链表存起来，然后就变成了寻找两个链表的公共结点的问题了。  
但是这个思路有一个问题需要解决，就是如何去找路径根节点到某个结点的路径，方法就是利用栈，先将某个不确定是不是路径上的结点压入，然后遍历其子树发现没有目标结点则确认该结点不在路径上，就可以再次弹出。实际就是深度优先遍历  
具体代码如下

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    import java.util.Deque;
    import java.util.LinkedList;
    class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            Deque<TreeNode> stack1 = new LinkedList<>();
            getPath(root,p,stack1);
            Deque<TreeNode> stack2 = new LinkedList<>();
            getPath(root,q,stack2);
    
            //判断栈的大小
            int length1 = stack1.size();
            int length2 = stack2.size();
            int length = 0;
            if(length1>length2){
        
                length = length1 - length2;
                while(length != 0){
        
                    stack1.pop();
                    length--;
                }
            }
            else{
        
                length = length2 - length1;
                while(length != 0){
        
                stack2.pop();
                length--;
                }
            }
            //栈元素个数都一样了
            while(!stack1.isEmpty() && !stack2.isEmpty()){
        
                if(stack1.peek() != stack2.peek()){
        
                    stack1.pop();
                    stack2.pop();
                }
                else{
        
                    return stack1.peek();
                }
            
            }
            return null;    
            
        }
        public  Boolean getPath(TreeNode root,TreeNode node,Deque<TreeNode> stack){
        
            if(root == null || node == null){
        
                return false;
            }
            stack.push(root);//根节点肯定在路径里面，第一个压入栈中,
            if(root == node){
        
                return true;
            }
            boolean ret1 = getPath(root.left,node,stack);//之后先把寻找过程中的结点都先压入栈中
            if(ret1 == true){
        
                return true;//往左边找找到了
            }
            boolean ret2 = getPath(root.right,node,stack);
            if(ret2 == true){
        
                return true;//往右边找找到了
            }
            //往左和往右都没找到，说明这个结点不在路径上，所以把这个点给弹出
            stack.pop();
            return false;
            
        }
    }

[34d396e926064f7f8311f69d999ed8ca.png]: https://img-blog.csdnimg.cn/34d396e926064f7f8311f69d999ed8ca.png
[b26df8dcbd3540a0bea470b6bf30ccea.png]: https://img-blog.csdnimg.cn/b26df8dcbd3540a0bea470b6bf30ccea.png
[415df088f92d42189c631d67617f3ea8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/204ac37b76e045fb94db5ab2371cf0c3.png
[21cc63add59b43aead484467193fec88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/07f45e089701450db8a5863776779942.png
[30cab77e6cbd4c568be069edc910185f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/3eaa99b12aff46c2beb44d5c1d874841.png
[287edadb7e494d3a9a504bf433056e58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/488901dbb22f44d1ac1ba616db30b18f.png