題目

標題和出處

標題：具有所有最深結點的最小子樹

出處：865. 具有所有最深結點的最小子樹

難度

5 級

題目描述

要求

給定二叉樹的根結點 $\text{root}$，每個結點的深度是該結點到根的最短距離。

返回包含原始樹中所有最深結點的最小子樹。

如果一個結點在整個樹的所有結點中具有最大的深度，則該結點是最深的。

一個結點的子樹是該結點加上它的所有后代的集合。

示例

示例 1：

輸入：$\text{root?=?[3,5,1,6,2,0,8,null,null,7,4]}$
輸出：$\text{[2,7,4]}$
解釋：
我們返回值為 $\text{2}$ 的結點，在圖中用黃色標記。
在圖中用藍色標記的是樹的最深的結點。
注意，結點 $\text{5}$、$\text{3}$ 和 $\text{2}$ 包含樹中最深的結點，但結點 $\text{2}$ 的子樹最小，因此我們返回它。

示例 2：

輸入：$\text{root?=?[1]}$
輸出：$\text{[1]}$
解釋：根結點是樹中最深的結點。

示例 3：

輸入：$\text{root?=?[0,1,3,null,2]}$
輸出：$\text{[2]}$
解釋：樹中最深的結點為 $\text{2}$，有效子樹為結點 $\text{2}$、$\text{1}$ 和 $\text{0}$ 的子樹，但結點 $\text{2}$ 的子樹最小。

數據范圍

• 樹中結點數目在范圍 $\text{[1,?500]}$ 內
• $\text{0}\le \text{Node.val}\le \text{500}$
• 樹中的所有值各不相同

解法一

思路和算法

由于所有最深結點的深度相同，因此對于包含所有最深結點的子樹，每個最深結點到子樹根結點的距離相同。只要定位到所有最深結點，即可找到包含所有最深結點的最小子樹的根結點。

為了定位到所有最深結點，可以使用層序遍歷。從根結點開始依次遍歷每一層的結點，在層序遍歷的過程中需要區分不同結點所在的層，確保每一輪訪問的結點為同一層的全部結點。遍歷每一層結點之前首先得到當前層的結點數，即可確保每一輪訪問的結點為同一層的全部結點。層序遍歷訪問的最后一層結點即為所有最深結點。

定位到所有最深結點之后，從最深結點向根結點移動，即每次從當前結點移動到父結點。由于每個最深結點到子樹根結點的距離相同，因此每個最深結點將同時移動到包含所有最深結點的最小子樹的根結點。使用哈希集合存儲每次移動之后的結點集合，每次移動之后，結點數量一定不變或減少，當只剩下一個結點時，該結點即為包含所有最深結點的最小子樹的根結點。

代碼

class Solution {public TreeNode subtreeWithAllDeepest(TreeNode root) {Map<TreeNode, TreeNode> parentMap = new HashMap<TreeNode, TreeNode>();List<TreeNode> deepest = new ArrayList<TreeNode>();Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {deepest.clear();int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();deepest.add(node);TreeNode left = node.left, right = node.right;if (left != null) {parentMap.put(left, node);queue.offer(left);}if (right != null) {parentMap.put(right, node);queue.offer(right);}}}Set<TreeNode> nodes = new HashSet<TreeNode>(deepest);while (nodes.size() > 1) {Set<TreeNode> parents = new HashSet<TreeNode>();for (TreeNode node : nodes) {parents.add(parentMap.get(node));}nodes = parents;}return nodes.iterator().next();}
}

復雜度分析

• 時間復雜度：$O(n)$，其中 $n$ 是二叉樹的結點數。層序遍歷訪問每個結點一次，需要 $O(n)$ 的時間，從所有最深結點移動到包含所有最深結點的最小子樹的根結點的時間不超過 $O(n)$，因此總時間復雜度是 $O(n)$。

• 空間復雜度：$O(n)$，其中 $n$ 是二叉樹的結點數。空間復雜度主要是隊列空間和哈希集合，隊列內元素個數不超過 $n$，哈希集合內元素個數不超過 $n$。

解法二

思路和算法

對于二叉樹中的每個結點，考慮其左子樹和右子樹的深度。如果左子樹和右子樹的深度相同，則左子樹和右子樹中都有最深結點，當前結點就是包含所有最深結點的最小子樹的根結點；如果左子樹和右子樹的深度不同，則所有最深結點一定在深度較大的子樹中，需要在深度較大的子樹中尋找包含所有最深結點的最小子樹的根結點。因此，尋找包含所有最深結點的最小子樹的根結點，等價于尋找左子樹和右子樹的深度相同的結點，以下將該結點稱為「目標結點」。

從根結點開始深度優先搜索，計算每個子樹的深度，并尋找目標結點。定義空樹的深度為 $0$，當子樹非空時，子樹的深度為左子樹的深度和右子樹的深度中的最大值加 $1$。

尋找目標結點的具體做法如下。

1. 如果當前結點的左子樹的深度和右子樹的深度相同，則當前結點即為目標結點，當前子樹的深度為左子樹的深度加 $1$。

2. 否則，在深度較大的子樹中尋找目標結點，當前子樹的深度為深度較大的子樹的深度加 $1$。

上述過程是一個遞歸的過程，遞歸的終止條件是當前結點為空或者當前結點的左子樹的深度和右子樹的深度相同，其余情況則調用遞歸。

對于每個結點，首先訪問其子結點尋找目標結點和計算子樹高度，然后根據訪問子結點的結果得到當前結點的結果。計算結果的順序是先計算子結點的結果，后計算當前結點的結果，該順序實質是后序遍歷。由于在計算每個結點的結果時，該結點的子結點的結果已知，該結點的結果由子結點的結果決定，因此可以確保結果正確。

代碼

class Solution {class NodeDepth {private TreeNode node;private int depth;public NodeDepth(TreeNode node, int depth) {this.node = node;this.depth = depth;}public TreeNode getNode() {return node;}public int getDepth() {return depth;}}public TreeNode subtreeWithAllDeepest(TreeNode root) {NodeDepth rootDepth = dfs(root);return rootDepth.getNode();}public NodeDepth dfs(TreeNode node) {if (node == null) {return new NodeDepth(node, 0);}NodeDepth left = dfs(node.left), right = dfs(node.right);TreeNode leftNode = left.getNode(), rightNode = right.getNode();int leftDepth = left.getDepth(), rightDepth = right.getDepth();if (leftDepth == rightDepth) {return new NodeDepth(node, leftDepth + 1);}return leftDepth > rightDepth ? new NodeDepth(leftNode, leftDepth + 1) : new NodeDepth(rightNode, rightDepth + 1);}
}

復雜度分析

• 時間復雜度：$O(n)$，其中 $n$ 是二叉樹的結點數。每個結點都被訪問一次。

• 空間復雜度：$O(n)$，其中 $n$ 是二叉樹的結點數。空間復雜度主要是深度優先搜索的過程中創建實例的空間和遞歸調用的棧空間，因此空間復雜度是 $O(n)$。