系列文章目录

前言

二叉树快完了，加油！！！

题录

236. 二叉树的最近公共祖先

题目链接如下：

这道题怎么做呢？其实是要分步骤进行

步骤一

给出根节点，和目标节点，然后查看目标节点是否为根节点的子树。这个很简单不是？

public boolean find(TreeNode root,TreeNode target){
          
   
        if(root == null) return false;
        if(root == target) return true;
        return find(root.left,target) || find(root.right,target);
    }

步骤二

那接下来肯定就是要分情况讨论了

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          
   
        //接下来就是进行判断
        if(root == null) return null;
        if(root == p || root == q) return root;//如果说p或者q任意一个为根节点，那祖先肯定是根节点
        //如果说p q节点都在左侧，那就去左子树找祖先
        if(find(root.left,p) && find(root.left,q)) return lowestCommonAncestor(root.left,p,q);
        //如果说p q节点都在右侧，那就去右子树找祖先
        if(find(root.right,p) && find(root.right,q)) return lowestCommonAncestor(root.right,p,q);
        //如果不同时在一侧，那当前节点肯定就是祖先
        return root;
    }

步骤三

第三步是什么呢？肯定就是化简啦，上面那样写肯定是可以的，但是有点长。先上代码吧，然后再对代码讲解一下

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          
   
        if(root == null || root == p || root == q) return root;//这一步是关键
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left == null && right == null) return null;
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }

这个代码就是把步骤一和步骤合并，但是这里吧…emmm，重点就是：后序遍历。和上面一样，分成两步来看

步骤一： 这是第一步，就是一个不断递归的过程，然后去寻找p和q节点。

这是第二步，是对寻找的情况进行判断。

这两步就是对每一层递归的分解，好像有点乱是不是？？emmm，先停一下，后续如果我可以组织好自己的语言再继续。

235. 二叉搜索树的最近公共祖先

题目链接：

其实是可以当做一个普通的树来进行处理的，但是这里既然提到了二叉搜索树，和上题一样，甚至代码都不用变动。

但是呢，这里既然提到了二叉搜索树，那么肯定是可以通过二叉搜索树的性质对当前时间复杂度进行优化。

public class 二叉搜索树的公共祖先 {
          
   
    //二叉树的公共祖先是后序遍历了，那这里我还可以后续遍历嘛？我第一思路是前序遍历
    //前序遍历还是有点小问题，return root重复了
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          
   
        if(root.val > p.val && root.val > q.val){
          
   
            return lowestCommonAncestor(root.left,p,q);
        }
        if(root.val < p.val && root.val < q.val){
          
   
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }
}