1123.最深叶节点的最近公共祖先

链接：1123.最深叶节点的最近公共祖先
难度：Medium
标签：树、深度优先搜索、广度优先搜索、哈希表、二叉树
简介：给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。

题解 1 - python

• 编辑时间：2023-09-06
• 执行用时：52ms
• 内存消耗：16.27MB
• 编程语言：python
• 解法介绍：bfs。

class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        prevq = []
        q: deque[TreeNode] = deque()
        q.append(root)
        size = 1
        m: dict[TreeNode, TreeNode] = {}
        while len(q):
            cur = q.popleft()
            prevq.append(cur)
            if cur.left:
                m[cur.left] = cur
                q.append(cur.left)
            if cur.right:
                m[cur.right] = cur
                q.append(cur.right)
            size -= 1
            if size == 0:
                size = len(q)
                if size:
                    prevq.clear()
        while len(set(prevq)) > 1:
            prevq = [m[item] for item in prevq]
        return list(set(prevq))[0]

题解 2 - cpp

• 编辑时间：2023-09-06
• 执行用时：8ms
• 内存消耗：20.18MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        function<pair<int, TreeNode*>(TreeNode*, int)> dfs = [&](TreeNode *node, int level) -> pair<int, TreeNode*> {
            pair<int, TreeNode*> res = make_pair(level, node);
            if (node->left) {
                res = dfs(node->left, level + 1);
            }
            if (node->right) {
                auto rres = dfs(node->right, level + 1);
                if (rres.first > res.first) res = rres;
                else if (rres.first == res.first) res.second = node;
            }
            return res;
        };
        return dfs(root, 0).second;
    }
};

题解 3 - python

• 编辑时间：2023-09-06
• 执行用时：52ms
• 内存消耗：16.27MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node: TreeNode, level: int) -> (int, TreeNode):
            res = (level, node)
            if node.left:
                res = dfs(node.left, level + 1)
            if node.right:
                right_result = dfs(node.right, level + 1)
                if right_result[0] > res[0]:
                    res = right_result
                elif right_result[0] == res[0]:
                    res = (res[0], node)
            return res
        return dfs(root, 0)[1]

题解 4 - rust

• 编辑时间：2023-09-06
• 内存消耗：2.05MB
• 编程语言：rust
• 解法介绍：同上。

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn lca_deepest_leaves(
        root: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        fn dfs(node: Rc<RefCell<TreeNode>>, level: usize) -> (usize, Rc<RefCell<TreeNode>>) {
            let mut res = (level, node.clone());
            let node_ref = node.as_ref().borrow();
            if let Some(ref left) = node_ref.left {
                res = dfs(left.clone(), level + 1);
            }
            if let Some(ref right) = node_ref.right {
                let rres = dfs(right.clone(), level + 1);
                if rres.0 > res.0 {
                    res = rres;
                } else if rres.0 == res.0 {
                    res.1 = node.clone();
                }
            }
            res
        }
        Some(dfs(root.unwrap().clone(), 0).1)
    }
}