二叉树最近的公共祖先

来自Leetcode第236题二叉树最近的公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

1
2
3

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

递归

在左、右子树中分别查找是否包含p或q：
如果以下两种情况（左子树包含p，右子树包含q/左子树包含q，右子树包含p），那么此时的根节点就是最近公共祖先
如果左子树包含p和q，那么到root->left中继续查找，最近公共祖先在左子树里面
如果右子树包含p和q，那么到root->right中继续查找，最近公共祖先在右子树里面

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)
         return right;
     if(right == null)
         return left;
     return root;
 }

来自官方题解的解答

先深度遍历改树。当你遇到节点 p 或 q 时，返回一些布尔标记。该标志有助于确定是否在任何路径中找到了所需的节点。最不常见的祖先将是两个子树递归都返回真标志的节点。它也可以是一个节点，它本身是p或q中的一个，对于这个节点,子树递归返回一个真标志。

算法：

从根节点开始遍历树。
如果当前节点本身是 p 或 q 中的一个，我们会将变量 mid 标记为 true，并继续搜索左右分支中的另一个节点。
如果左分支或右分支中的任何一个返回 true，则表示在下面找到了两个节点中的一个。
如果在遍历的任何点上，左、右或中三个标志中的任意两个变为 true，这意味着我们找到了节点 p 和 q 的最近公共祖先。

class Solution {

    private TreeNode ans;

    public Solution() {
        // Variable to store LCA node.
        this.ans = null;
    }

    private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {

        // If reached the end of a branch, return false.
        if (currentNode == null) {
            return false;
        }

        // Left Recursion. If left recursion returns true, set left = 1 else 0
        int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;

        // Right Recursion
        int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;

        // If the current node is one of p or q
        int mid = (currentNode == p || currentNode == q) ? 1 : 0;


        // If any two of the flags left, right or mid become True
        if (mid + left + right >= 2) {
            this.ans = currentNode;
        }

        // Return true if any one of the three bool values is True.
        return (mid + left + right > 0);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Traverse the tree
        this.recurseTree(root, p, q);
        return this.ans;
    }
}

使用父指针迭代

还是来自官方题解

如果每个节点都有父指针，那么我们可以从 p 和 q 返回以获取它们的祖先。在这个遍历过程中，我们得到的第一个公共节点是 LCA 节点。我们可以在遍历树时将父指针保存在字典中。

算法：

从根节点开始遍历树。
在找到 p 和 q 之前，将父指针存储在字典中。
一旦我们找到了 p 和 q，我们就可以使用父亲字典获得 p 的所有祖先，并添加到一个称为祖先的集合中。
同样，我们遍历节点 q 的祖先。如果祖先存在于为 p 设置的祖先中，这意味着这是 p 和 q 之间的第一个共同祖先（同时向上遍历），因此这是 LCA 节点。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    Stack<TreeNode> stack = new Stack<>();
    HashMap<TreeNode, TreeNode> parent = new HashMap<>();
    stack.push(root);
    parent.put(root, null);
    //将遍历过程中每个节点的父节点保存起来
    while (!parent.containsKey(p) || !parent.containsKey(q)) {
        TreeNode cur = stack.pop();
        if (cur.left != null) {
            stack.push(cur.left);
            parent.put(cur.left, cur);
        }
        if (cur.right != null) {
            stack.push(cur.right);
            parent.put(cur.right, cur);
        }
    }
    HashSet<TreeNode> path = new HashSet<>();
    // 倒着还原 p 的路径，并将每个节点加入到 set 中
    while (p != null) {
        path.add(p);
        p = parent.get(p);
    }

    // 倒着遍历 q 的路径，判断是否在 p 的路径中
    while (q != null) {
        if (path.contains(q)) {
            break;
        }
        q = parent.get(q);
    }
    return q;
}