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

Categories:

题目描述
思路分析
1. 解法一：后序遍历返回深度（推荐）
相似题目

题目描述

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

思路分析

解法一：后序遍历返回深度（推荐）

核心思路：

后序遍历返回每个节点子树的最大深度。

若左右深度相等，当前节点就是最深叶的 LCA。

若不等，向深度更大的子树返回结果。

复杂度分析：

时间复杂度：O(n)，其中 n 为节点数。

空间复杂度：O(h)，其中 h 为树高。

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        return dfs(root).node;
    }

    private Result dfs(TreeNode node) {
        if (node == null) {
            return new Result(null, 0);
        }
        Result left = dfs(node.left);
        Result right = dfs(node.right);
        if (left.depth == right.depth) {
            return new Result(node, left.depth + 1);
        }
        if (left.depth > right.depth) {
            return new Result(left.node, left.depth + 1);
        }
        return new Result(right.node, right.depth + 1);
    }

    private static class Result {
        TreeNode node;
        int depth;
        Result(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }
}

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
    node, _ := dfsDeepest(root)
    return node
}

func dfsDeepest(node *TreeNode) (*TreeNode, int) {
    if node == nil {
        return nil, 0
    }
    leftNode, leftDepth := dfsDeepest(node.Left)
    rightNode, rightDepth := dfsDeepest(node.Right)

    if leftDepth == rightDepth {
        return node, leftDepth + 1
    }
    if leftDepth > rightDepth {
        return leftNode, leftDepth + 1
    }
    return rightNode, rightDepth + 1
}

相似题目

题目	难度	考察点
236. 二叉树的最近公共祖先	中等	LCA
543. 二叉树的直径	简单	后序遍历
865. 具有所有最深节点的最小子树	中等	DFS
1123. 最深叶节点的最近公共祖先	中等	DFS
124. 二叉树中的最大路径和	困难	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/85791774