题目大意

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

　　二叉树最近邻公共祖先问题

题目分析

　　利用递归即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        if (p == root || q == root) {
            return root;
        }
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        if (l != null && r != null) {
            return root;
        }
        if (l == null) {
            return r;
        }
        return l;
    }
}

　　时间复杂度O(n)，n是树的节点个数

equals方法

　　Object类中的equals方法用于检测对象是否相等，Object 类中equals方法：

1
2
3

public boolean equals(Object obj) {
  return (this == obj);
}

　　包含一个或者多个抽象方法的类本身必须被声明为抽象的。抽象方法需要使用abstract关键字，不需要实现抽象类中抽象方法的内容，为了提高程序的清晰可读性，包含抽象方法的类本身必须被声明为abstract的。当然，抽象类也可以包含具体数据和具体方法。

　　扩展抽象类可以有两种选择，一是在子类中的抽象方法也不实现，这样就必须将子类标记为抽象类，二是定义或者说实现全部抽象方法，这样，子类就不是抽象方法了。

　　注意，类不含抽象方法也可以声明为抽象类，抽象类不能被实例化，当然可以定义一个抽象类的变量，引用非抽象子类的对象，例如：

1

Person p = new Student("John");

　　这里，Person是抽象类，Student是Person的非抽象子类。

static关键字

　　java中static关键字主要有以下几种用途

1. 静态变量

   1 2 3

   class Employee { private static int id = 1; }

2. 静态常量

   1 2 3 4 5

   public class Math { ... public static final double PI = 3.1415.....; ... }

3. 静态方法

　　静态方法是一种不能对对象实施操作的方法，例如Math类的pow方法，也就是说没有隐式的参数，或者没有this指针的方法。但是静态方法可以访问类的静态域。一般我们会在以下两种场景使用静态方法：一是方法不需要访问对象状态，所需参数都是通过显示参数提供。二是一个方法只需要访问类的静态域

final关键字

　　java中static关键字主要有以下几种用途

1. final类，如果是final的class，用处就是阻止继承，所以final类永远不会有子类，final类的声明对象在进行方法调用时不会进行动态绑定。
2. final方法，方法如果是final，就是子类不能覆盖这个方法。