题解 | #农场牛群族谱#

1. 题目考察的知识点

二叉树的遍历

2. 题目解答方法的文字分析

本算法主要结构是，用dfs算法遍历整棵二叉树，找到最近公共祖先，然后返回它的值

dfs算法详解： 1、p和q在二叉树两侧，则找最近的root结点。 2、p和q在二叉树同侧，则找p或者q。 具体的判断为： (1)如果left和right均不为空，说明p和q一个在左子树一个在右子树，返回当前root节点； (2)如果left为空，right不为空，说明p和q都在右子树中，返回right； (3)如果left不为空，right为空，说明p和q都在左子树中，返回left。

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
      TreeNode ans =  dfs(root,p,q);
      if(ans ==null){
        return -1;
      }else{
        return ans.val;
      }
    }
     public TreeNode dfs(TreeNode root, int p, int q) {
        // 如果root为空或者如果 p和q中有等于 root.val的，那么它们的最近公共祖先即为root
        if(root == null || root.val == p || root.val == q) return root;
        // 递归遍历左子树，只要在左子树中找到了p或q,就返回。
        TreeNode left = dfs(root.left, p, q);
        // 同理
        TreeNode right = dfs(root.right, p, q);
        // 如果在左子树中 p和 q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先
        if(left == null) return right;
        // 同理， p和 q一定都在左子树中
        if(right == null) return left;
        // left和 right均不为空时，说明 p、q节点分别在 root异侧, 最近公共祖先即为 root
        return root;
    }
}