当前位置：首页 > article >正文

Leetcode236经典题目二叉树的最近公共祖先

article 2024/9/22 7:23:03

本次为大家带来的题目是leetcode236二叉树的最近公共祖先
在这里插入图片描述
本道题的直观思路是自底向上进行寻找，如果存在的话那么向上返回，如何能够自底向上遍历呢？我们可以利用回溯进行处理，那么需要注意的是进行回溯的时候一定要使用后序遍历来操作，因为后序遍历的顺序是左、右、根，那么在根节点也就是我们进行判断的操作了。
下面说下可能存在的情况
1.如果当前节点的左和右子树都不为空，那么说明找到了公共祖先，直接返回。
2.假如节点左子树为空，右子树不为空，说明我们要继续向上返回。同理右子树为空左子树不为空也要返回。
具体的代码实现如下：

class Solution {
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //终止条件
        if(root==null) return null;
        //如果当前节点为q或p直接返回
        if(root==p||root==q) return root;
        //后序遍历
        //左
       TreeNode left = lowestCommonAncestor(root.left,p,q);
       //右
       TreeNode right = lowestCommonAncestor(root.right,p,q);
       //根
       //左右都不为空，说明存在q，p
       if(left!=null&&right!=null){
        return root;
       }else if(left!=null &&right==null){
        return left;
       }else if(right!=null&&left==null){
        return right;
       }else{
        return null;
       }

    }
}