[TOC]

1. 矩阵中的路径

image-20201113082513982

解题思路

本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝 解决。

  • 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。

  • 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。

DFS 解析： f

  • 递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。

  • 终止条件：

    1. 返回 false ： (1) 行或列索引越界

      ​ (2) 当前矩阵元素与目标字符不同

      ​ (3) 当前矩阵元素已访问过 （ (3) 可合并至 (2) ）

    2. 返回 true ： k = len(word) - 1 ，即字符串 word 已全部匹配。

  • 递推工作：

    1. 标记当前矩阵元素： 将 board[i][j] 修改为 空字符 ‘\0’ ，代表此元素已访问过，防止之后搜索时重复访问。
    2. 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
    3. 还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。

  • 返回值： 返回布尔量 res ，代表是否搜索到目标字符串。

    使用空字符（Python: ‘’ , Java/C++: ‘\0’ ）做标记是为了防止标记字符与矩阵原有字符重复。当存在重复时，此算法会将矩阵原有字符认作标记字符，从而出现错误。

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/58d5vh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean exist(char[][] board, String word) {
    char[] words = word.toCharArray();
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (dfs(board, words, i, j, 0))
                return true;
        }
    }
    return false;
}

private boolean dfs(char[][] board, char[] words, int i, int j, int k) {
    // i 或 j 越界，或者字符不匹配，则直接返回 false
    if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k])
        return false;
    if (k == words.length - 1)
        return true;
    board[i][j] = '\0';
    boolean res = dfs(board, words, i + 1, j, k + 1) || dfs(board, words, i - 1, j, k + 1)
            || dfs(board, words, i, j + 1, k + 1) || dfs(board, words, i, j - 1, k + 1);
    board[i][j] = words[k];
    return res;
}

2. 机器人的运动范围

image-20201121093611682

解题思路

  • 数位之和计算

    数位之和计算通法：

    1
    2
    3
    4
    5
    6
    7
    8
    int sums(int x) {
        int sum = 0;
        while(x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }

    在本题中，机器人每次移动一格，x 的增量为 1，故：

    数位之和计算可简化为：

    1
    (x + 1) % 10 != 0 ? s_x + 1 : s_x - 8;

  • 易知，机器人可 仅通过向右和向下移动，访问所有可达解 。

  • 综上，可使用深度优先遍历：

    • 终止条件：
      1. 遍历数组下标越界
      2. 数组下标之和大于 k
      3. 该位置已被访问过
    • 将当前位置设置为已访问
    • 返回 1 + dfs(向下) + dfs(向右)

代码实现

可以使用本题简化后的数位之和运算方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    boolean visited[][];
    int m, n, k;

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }

    private int dfs(int i, int j, int si, int sj) {
        if (i >= m || j >= n || si + sj > k || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + 
                dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) +
                dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
}

也可使用最基本的数位之和运算方法进行解答，代码更易懂，但效率相对会低一点：

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
29
30
31
32
class Solution {

    boolean visited[][];
    int m, n, k;

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0);
    }
    
    private int dfs(int i, int j) {
        if (i >= m || j >= n || sums(i, j) > k || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j) + dfs(i, j + 1);
    }

    private int sums(int x, int y) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        while (y > 0) {
            sum += y % 10;
            y /= 10;
        }
        return sum;
    }
}

3. 树的子结构

image-20201121102743432

解题思路

参考：图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

  • 判断 B 树是否为 A 树的子树，需要依次判断 B 树是否为 A 树某个节点的子树，该过程可分为两步：

    1. 遍历 A 树的每个节点 node_i （对应函数 isSubStructure(A, B)）

    2. 判断 B 树是否为节点 node_i 的子树 （对应函数 recur(A, B)）

  • recur(A , B)

    • 终止条件：
      1. B 树到底，说明 B 树是该节点的子树，返回 true
      2. A 树(该节点)到底，说明该节点不包含 B 树，返回 false
      3. A 树(该节点)与 B 树的值不相等，返回 false
    • 返回值：
      1. 判断当前节点的左子树是否与 B 树的左子树相等
      2. 判断当前节点的右子树是否与 B 树的右子树相等

  • isSubStructure(A, B)

    • 排除特殊情况：A 树 或者 B 树为空
    • B 树是 A 树根节点的子树 recur(A, B)
    • B 树是 A 树 左子节点的子树 isSubStructure(A.left, B)
    • B 树是 A 树 右子节点的子树 isSubStructure(A.right, B)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean recur (TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

4. 二叉树的镜像 🔥

image-20201121104553494

解题思路

参考：图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

递归遍历整个二叉树，交换每个节点的左右子节点，即可得到镜像的二叉树

  • 终止条件：当节点为空时，返回 null

  • 递推工作：交换左右子节点（类似于交换两个值）

    1. TreeNode temp = root.left;

    2. root.left = mirrorTree(root.right);

    3. root.right = mirrorTree(temp);

  • 返回结果： root

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        return root;
    }
}

5. 对称的二叉树

image-20201121113002400

解题思路

参考：图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

  • 对于对称的二叉树，一定有：

    • L.val = R.val
    • L.left.val = R.right.val
    • L.left.val = R.right.val

  • recur(left, right)

    • 终止条件：

      1. 当 L 和 R 同时越过叶节点： 此树从顶至底的节点都对称，因此返回 true
      2. 当 L 或 R 中只有一个越过叶节点： 此树不对称，因此返回 false
      3. 当节点 L 值 != 节点 R 值： 此树不对称，因此返回 false

    • 返回值：

      两对节点都对称时，才是对称树，因此用与逻辑符 && 连接。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || recur(root.left, root.right);
    }

    private boolean recur(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}

6. 从上到下打印二叉树 🔥

image-20201123170957052

解题思路

参考：图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

从上至下打印二叉树一般使用 BFS（广度优先搜索）。

BFS 通常借助 队列 的先入先出的特性来实现。

  • 特殊处理：root == null
  • 初始化：List、Queue
  • BFS循环
    • 队首元素出队
    • 将队首元素的值添加到 List 中
    • 添加不为空的子节点至队列中
  • 将 List 转为 整性数组 并返回

代码实现

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
29
30
31
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        // 1. 特殊处理
        if (root == null) return new int[0];
        // 2. 初始化
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        queue.add(root);
        // 3. BFS循环
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        // 4. 将 List 转化为 数组
        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++) 
            res[i] = ans.get(i);
        return res;
    }
}

7. 从上到下打印二叉树 II

image-20201123173037014

解题思路

大致思路同 从上到下打印二叉树

变化在于在 BFS循环 中，队列 Queue 的长度即为每一层的节点数！

代码实现

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
29
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<List<Integer>>();
        List<List<Integer>> res = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> temp = new LinkedList<>();
            // 队列 queue 的长度即为每一层的节点数
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

8. 二叉树中和为某一值的路径

image-20201123175344652

解题思路

参考：图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

二叉树方案搜索问题，使用回溯法解决，包含 先序遍历 + 路径记录

  • 先序遍历： 按照 “根、左、右” 的顺序，遍历树的所有节点。

  • 路径记录： 在先序遍历中，记录从根节点到当前节点的路径。当路径满足

    ① 根节点到叶节点形成的路径

    ② 各节点值的和等于目标值 sum

    时，将此路径加入结果列表。

代码实现

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
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }
	
    // root：当前节点 	tar：当前目标值
    void recur(TreeNode root, int tar) {
        // 终止条件
        if(root == null) return;
        // 路径更新
        path.add(root.val);
        // 目标值更新
        tar -= root.val;
        // 路径记录，将满足条件的路径添加到结果中
        if (root.left == null && root.right == null && tar == 0) 
            res.add(new LinkedList(path));
        // 不满足条件，继续递归
        recur(root.left, tar);
        recur(root.right, tar);
        // 路径恢复：向上回溯前需要将当前节点从路径中删除
        path.removeLast();
    }
}

9. 二叉搜索树与双向链表

image-20201127102646145

解题思路

参考：图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

题目要求将二叉搜索树转化为排序的双向循环链表

按顺序遍历二叉搜索树需要用到中序遍历！

这里我们需要用到两个函数 treeToDoublyList(Node root) 、 dfs(Node cur)

  • dfs(Node cur)

    用来中序遍历 BST，在遍历过程中生成双向链表

    • 特殊情况：当前节点为空，直接返回

    • 生成双向链表：

      如果上一个节点为空，则说明没有头节点，将当前节点置为头节点

      pre.right = cur

      cur.left = pre

      pre 节点后移一位，指向当前节点

  • treeToDoublyList(Node root)：

    该函数用来生成完整的双向循环链表

    • 特殊情况：当前节点为空，直接返回
    • 生成双向链表：dfs(root)
    • 生成循环链表：头尾相连
    • 返回头节点 head

代码实现

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 Node.
class Node {
    public int val;
    public Node left;
    public Node right;
};
*/
class Solution {
    Node head, pre;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    void dfs(Node cur) {
        if (cur == null) return;
        dfs(cur.left);
        if(pre != null) pre.right = cur
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right); 
    }
}

10. 序列化二叉树

image-20201127105322127

解题思路

参考：图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

序列化 使用层序遍历实现。反序列化 通过各层节点之间的关系建立序列中的索引，进而实现。

  • 序列化

    • 特数情况： root 为空，直接返回 []

    • 建立 StringBulider（存储序列化后的二叉树）、Queue （进行层序遍历）

      node 不为空：将 node 的值加入结果

      node 为空：将 null 加入结果

    • 需要注意的小细节：

      1. 结果的首尾需要加上 []
      2. 序列化后得每个字符之间通过 , 隔开，故需要每次加入值时加入 , 同时最后删除多余的 ,

  • 反序列化

    基本操作同上，但需要设置一个索引 i 来记录得到的字符串数组的下标，每当有不为 i++ ，判断 vals[i] 是否为 null，不为null 则用它的值建立树，并与二叉树相连

    • 需要注意的小细节：
      1. 处理字符串数组可使用 data.substring(1, data.length() - 1).split(",")
      2. 使用字符串数组中的值初始化树节点时注意将值转为整型

代码实现

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>(){{add(root);}};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            } else {
                res.append("null,");
            }
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>(){{add(root);}};
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

绝活

看到0ms的大神🤷‍♀️

  • 设置全局变量保存 root

  • 结果的输出与第一个函数输出无关

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Codec {
    private TreeNode root;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        this.root =root;
        return null;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return root;
    }
}

11. 二叉树的深度 🔥

image-20201127151908392

解题思路

基础题，一般情况可用递归两行代码搞定！

  • 思路一：递归遍历二叉树，返回 1 + 深度较大的子树的层数
  • 思路二：层序遍历二叉树，设置变量记录遍历最大层数

代码实现

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
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    // 递归遍历
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
    
    // 层序遍历
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
        int res = 0;
        while(!queue.isEmpty()) {
            // 初始化一个空列表 tmp ，用于临时存储下一层节点；
            tmp = new LinkedList<>();
            for(TreeNode node : queue) {
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
        return res;
    }
}

12. 求1+2+…+n

image-20201127153506025

解题思路

  • 本题禁止使用乘除法，不然可以用公式：

$$
sum = n * (n - 1) / 2
$$

  • 也禁止用条件判断、循环语句，不然可以直接循环或者递归求和：

    1
    2
    3
    4
    5
    6
    public int sumNums(int n) {
        // if 语句不让用
        if(n == 1) return n;
        n += sum(n - 1);
        return n;
    }

  • 所以我们考虑使用布尔运算的短路效应来替代 if 语句：

    boolean x = (n > 1) && ...

    • 当 n > 1 时，会执行后面的判断语句
    • 当 n <= 1 时，会直接得出结果 false 从而不执行后面的语句

代码实现

1
2
3
4
5
6
class Solution {
    public int sumNums(int n) {
        boolean x = n > 1 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

绝活

使用 C++ 构造二维数组，直接求 二维数组的大小的一半，就是结果

从而间接实现
$$
sum = \frac{n * (n - 1)} {2}
$$

1
2
3
4
5
6
7
8
// c++ 一步到位
class Solution {
public:
    int sumNums(int n) {
        bool arr[n][n+1];
        return sizeof(arr)>>1;
    }
};

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

image-20201127175822734

解题思路

参考：图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

由二叉搜索树的性质可知两个子树的公共祖先的值一定在两个子树的值之间

image-20201127180601259

故可分三种情况进行递归：

  1. 子树的值都比当前节点小：

    公共祖先在当前节点的左侧，向左进行递归

  2. 子树的值都比当前节点大：

    公共祖先在当前节点的右侧，向右进行递归

  3. 子树的值在当前节点之间：

    返回当前节点

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 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.val > p.val && root.val > q.val) 
            return lowestCommonAncestor(root.left, p, q);
        else if (root.val < p.val && root.val < q.val) 
            return lowestCommonAncestor(root.right, p, q);
        return root;  
    }
}

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

image-20201127181040078

解题思路

大体思路同 二叉树的最近公共祖先

代码实现

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
29
30
31
32
33
34
35
36
37
class Solution {
    /**
     * 二叉树的最近公共祖先
     * 思路：
     * 三种情况：
     * 1、p q 一个在左子树 一个在右子树 那么当前节点即是最近公共祖先
     * 2、p q 都在左子树 
     * 3、p q 都在右子树
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (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) {
            // p q 一个在左，一个在右
            return root;
        }
        if (left != null) {
            // p q 都在左子树
            return left;
        }
        if (right != null) {
            // p q 都在右子树
            return right;
        }
        return null;
    }
}