LeetCode.236.Lowest Common Ancestor of a Binary Tree 二叉树的最近公共祖先

题目描述

236 Lowest Common Ancestor of a Binary Tree
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

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]

BST

Example 1:

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

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
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.

---

相似题目

LeetCode.235.Lowest Common Ancestor of BST BST的最近公共祖先
LeetCode.236.Lowest Common Ancestor of a Binary Tree 二叉树的最近公共祖先

---

解题过程

Map记录每个结点的父节点

1、先遍历一遍二叉树，用一个 Map 记录每个结点的父节点
2、从 p 开始在 Map 中依次向上追溯其父节点，放入一个集合 visited
3、从 q 开始在 Map 中依次向上追溯其父节点，遇到的第一个在集合 visited 中的结点就是 p,q 的最近公共祖先

找p,q的祖先序列后再遍历祖先序列

先序遍历二叉树，过程中分别记录 p,q 的祖先序列，遍历结束后再遍历 p,q 的祖先序列找下标最大的值相同结点。
时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV202005 {
    private List<TreeNode> pAncestorList, qAncestorList;
    private TreeNode p, q;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.p = p;
        this.q = q;
        // 先序遍历并记录 p,q 的祖先序列
        preOrder(root, new LinkedList<>());
        TreeNode lowestCommonAncestor = new TreeNode(0);
        // 遍历 p,q 的祖先序列，找下标最大的公共结点
        for (int i = 0, j = 0; i < pAncestorList.size() && j < qAncestorList.size(); i ++, j++) {
            if (pAncestorList.get(i).val == qAncestorList.get(j).val) {
                lowestCommonAncestor = pAncestorList.get(i);
            }
        }
        return lowestCommonAncestor;
    }
    // 先序遍历二叉树， 遇到 p,q 时记录其祖先序列， ancestorList 是 root 的祖先序列
    public void preOrder(TreeNode root, Deque<TreeNode> ancestorList) {
        if (root == null) {
            return;
        }
        ancestorList.addLast(root);
        if (root.val == p.val) {
            pAncestorList = new ArrayList<>(ancestorList);
        }
        if (root.val == q.val) {
            qAncestorList = new ArrayList<>(ancestorList);
        }
        if (Objects.nonNull(root.left)) {
            preOrder(root.left, ancestorList);
            // 注意回溯
            ancestorList.removeLast();
        }
        if (Objects.nonNull(root.right)) {
            preOrder(root.right, ancestorList);
            // 注意回溯
            ancestorList.removeLast();
        }
    }
}

O(n^2)递归解法

使用了 235 题的同一份代码提交的，O(n^2) 时间复杂度，900ms，打败5%，性能很差。
containNodes 方法判断 root 中是否包含 p,q 结点，然后递归的对所有结点调用 containNodes 方法

private static class SolutionV202001 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (null == root) {
            return root;
        }
        if (containNodes(root.left, p, q)) {
            return lowestCommonAncestor(root.left, p, q);
        } else if(containNodes(root.right, p, q)) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
    // 非递归先序遍历，判断root中是否包含p和q
    public boolean containNodes(TreeNode root, TreeNode p, TreeNode q) {
        if (null == root) {
            return false;
        }
        boolean hasP = false;
        boolean hasQ = false;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode cur = root;
        while (!stack.isEmpty() || null != cur) {
            while (null != cur) {
                hasP = cur == p || hasP;
                hasQ = cur == q || hasQ;
                cur = cur.left;
                if (null != cur) {
                    stack.push(cur);
                }
            }
            cur = stack.pop();
            if (null != cur.right) {
                stack.push(cur.right);
            }
            cur = cur.right;
        }
        return hasP && hasQ;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_236_LowestCommonAncestorOfBinaryTree.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_236_LowestCommonAncestorOfBinaryTree.java

---