Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

    According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

    Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

    image.png

    Example 1:

    1. Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    2. Output: 3
    3. Explanation: The LCA of nodes 5 and 1 is 3.

    Example 2:

    1. Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    2. Output: 5
    3. Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

    Note:

    • All of the nodes’ values will be unique.
    • p and q are different and both values will exist in the binary tree.

    题意

    在一个普通二叉树中找到两个指定结点的最近公共祖先。

    思路

    递归：递归搜索整棵树，对于当前结点x，如果能在它的左边和右边找到p和q，或者x就是p、q中的一个，并且在它的左边或右边能找到另一个指定结点，那么x就是要求的最近公共祖先。

    迭代Hash：遍历整棵树，记录所有结点的父结点信息。从p出发，将p和其所有父结点存入set；再从q出发，沿父结点向上遍历，则第一个在set中出现的结点就是所求的最近公共祖先。

    代码实现 - 递归

    1. class Solution {
    2.     private TreeNode lca;
    4.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    5.         findTree(root, p, q);
    6.         return lca;
    7.     }
    9.     // 只要能找到p或q就返回true
    10.     private boolean findTree(TreeNode x, TreeNode p, TreeNode q) {
    11.         if (x == null) {
    12.             return false;
    13.         }
    15.         boolean self = x == p || x == q;
    16.         boolean left = findTree(x.left, p, q);
    17.         boolean right = findTree(x.right, p, q);
    19.         // 满足三种情况任意一种就能确定找到了lca
    20.         if (left && right || self && right || self && left) {
    21.             lca = x;
    22.         }
    24.         return self || left || right;
    25.     }
    26. }

    代码实现 - 迭代Hash

    1. class Solution {
    2.     Map<TreeNode, TreeNode> parent = new HashMap<>();
    4.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    5.         dfs(root, null);
    7.         Set<TreeNode> ancestors = new HashSet<>();
    9.         while (p != null) {
    10.             ancestors.add(p);
    11.             p = parent.get(p);
    12.         }
    14.         while (!ancestors.contains(q)) {
    15.             q = parent.get(q);
    16.         }
    18.         return q;
    19.     }
    21.     // 生成HashMap
    22.     private void dfs(TreeNode cur, TreeNode pre) {
    23.         if (cur == null) {
    24.             return;
    25.         }
    27.         parent.put(cur, pre);
    28.         dfs(cur.left, cur);
    29.         dfs(cur.right, cur);
    30.     }
    31. }