LeetCode 865. 具有所有最深节点的最小子树

Categories:

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

题目描述

✅ 865. 具有所有最深节点的最小子树

思路分析

解法一：递归后序遍历（推荐）

核心思路：

对每个节点，递归计算左右子树的最大深度

若左右子树深度相等，则当前节点就是包含所有最深节点的最小子树的根

若左子树更深，则答案在左子树中；若右子树更深，则答案在右子树中

返回值包含两个信息：当前子树的根节点（答案候选）和当前子树的最大深度

复杂度分析：

时间复杂度：O(n)，其中 n 为节点数，每个节点恰好访问一次

空间复杂度：O(h)，其中 h 为树的高度，递归栈空间

class Solution {
  public TreeNode subtreeWithAllDeepest(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;
    }
  }
}

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type result struct {
    node  *TreeNode
    depth int
}

func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
    return dfs(root).node
}

func dfs(node *TreeNode) result {
    if node == nil {
        return result{nil, 0}
    }

    left := dfs(node.Left)
    right := dfs(node.Right)

    // 左右深度相等，当前节点即为答案
    if left.depth == right.depth {
        return result{node, left.depth + 1}
    }

    // 深度更大的一侧包含所有最深节点
    if left.depth > right.depth {
        return result{left.node, left.depth + 1}
    }

    return result{right.node, right.depth + 1}
}

相似题目

题目	难度	考察点
1123. 最深叶节点的最近公共祖先	中等	递归、树
236. 二叉树的最近公共祖先	中等	递归、树
104. 二叉树的最大深度	简单	递归、BFS
543. 二叉树的直径	简单	递归、树
687. 最长同值路径	中等	递归、树
337. 打家劫舍 III	中等	递归、动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2020/38136477