https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves
1123. Lowest Common Ancestor of Deepest Leaves
給你一個二元樹，找出最深葉子節點的最近共通祖先。
思路：
1.先找出葉子節點的深度。
2.DFS遞迴處理，考慮：
如果當前節點是葉子節點(用最大深度判斷)，直接返回當前節點
如果當前節點的左子樹有葉子節點，當前節點是祖先，返回當前節點
如果當前節點的右子樹有葉子節點，當前節點是祖先，返回當前節點
如果當前節點的左右子樹都沒葉子節點，返回null
最後返回的就是祖先
Java Code:
-----------------------------------------------------------------
class Solution {
private int maxDepth;
public TreeNode lcaDeepestLeaves(TreeNode root) {
maxDepth = 0;
getMaxDepth(root, 0);
return lcaDeepestLeaves(root,0);
}
private void getMaxDepth(TreeNode root, int level) {
if (root == null) {
return;
}
maxDepth = Math.max(maxDepth, level);
getMaxDepth(root.left, level + 1);
getMaxDepth(root.right, level + 1);
}
private TreeNode lcaDeepestLeaves(TreeNode root, int level) {
if (root == null) {
return null;
}
if (level == maxDepth) {
return root;
}
TreeNode left = lcaDeepestLeaves(root.left, level + 1);
TreeNode right = lcaDeepestLeaves(root.right, level + 1);
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
return right;
}
}
-----------------------------------------------------------------
--
https://i.imgur.com/O931L58.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.104.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1743757930.A.975.html