Formatted question description: https://leetcode.ca/all/1123.html

1123. Lowest Common Ancestor of Deepest Leaves (Medium)

Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

The node of a binary tree is a leaf if and only if it has no children
The depth of the root of the tree is 0. if the depth of a node is d, the depth of each of its children is d + 1.
The lowest common ancestor of a set S of nodes, is the node A with the largest depth such that every node in S is in the subtree with root A.

Note: This question is the same as 865: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest leaf-nodes of the tree.
Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.

Example 2:

Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree, and it's the lca of itself.

Example 3:

Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.

Constraints:

The number of nodes in the tree will be in the range [1, 1000].
0 <= Node.val <= 1000
The values of the nodes in the tree are unique.

Related Topics:
Tree, Depth-first Search

Similar Questions:

Lowest Common Ancestor of a Binary Tree IV (Medium)

Solution 1.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        List<TreeNode> deepestLeaves = new ArrayList<TreeNode>();
        Map<TreeNode, TreeNode> childParentMap = new HashMap<TreeNode, TreeNode>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            deepestLeaves.clear();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                TreeNode left = node.left, right = node.right;
                if (left == null && right == null)
                    deepestLeaves.add(node);
                if (left != null) {
                    childParentMap.put(left, node);
                    queue.offer(left);
                }
                if (right != null) {
                    childParentMap.put(right, node);
                    queue.offer(right);
                }
            }
        }
        if (deepestLeaves.size() == 1)
            return deepestLeaves.get(0);
        Set<TreeNode> set = new HashSet<TreeNode>();
        for (TreeNode node : deepestLeaves) {
            TreeNode parent = childParentMap.get(node);
            set.add(parent);
        }
        while (set.size() > 1) {
            List<TreeNode> list = new ArrayList<TreeNode>(set);
            set.clear();
            for (TreeNode node : list) {
                TreeNode parent = childParentMap.get(node);
                set.add(parent);
            }
        }
        List<TreeNode> resultList = new ArrayList<TreeNode>(set);
        return resultList.get(0);
    }
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        return dfs(root).getKey();
    }

    private Pair<TreeNode, Integer> dfs(TreeNode root) {
        if (root == null) {
            return new Pair<>(null, 0);
        }
        Pair<TreeNode, Integer> l = dfs(root.left);
        Pair<TreeNode, Integer> r = dfs(root.right);
        int d1 = l.getValue(), d2 = r.getValue();
        if (d1 > d2) {
            return new Pair<>(l.getKey(), d1 + 1);
        }
        if (d1 < d2) {
            return new Pair<>(r.getKey(), d2 + 1);
        }
        return new Pair<>(root, d1 + 1);
    }
}

// OJ: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
// Time: O(N)
// Space: O(H)
class Solution {
    int maxDepth = -1, target = 0, cnt = 0;
    void count(TreeNode *root, int d) {
        if (!root) return;
        if (d > maxDepth) {
            target = 1;
            maxDepth = d;
        } else if (d == maxDepth) ++target;
        count(root->left, d + 1);
        count(root->right, d + 1);
    }
    TreeNode *find(TreeNode *root, int d) {
        if (!root) return NULL;
        int before = cnt;
        auto left = find(root->left, d + 1);
        if (left) return left;
        auto right = find(root->right, d + 1);
        if (right) return right;
        if (d == maxDepth) ++cnt;
        return before == 0 && cnt == target ? root : NULL;
    }
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        count(root, 0);
        return find(root, 0);
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(root):
            if root is None:
                return None, 0
            l, d1 = dfs(root.left)
            r, d2 = dfs(root.right)
            if d1 > d2:
                return l, d1 + 1
            if d1 < d2:
                return r, d2 + 1
            return root, d1 + 1

        return dfs(root)[0]

############

# 1123. Lowest Common Ancestor of Deepest Leaves
# https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        
        def helper(node):
            if not node: return 0, None
            
            h1, lca1 = helper(node.left)
            h2, lca2 = helper(node.right)
            
            if h1 > h2: return h1 + 1, lca1
            if h1 < h2: return h2 + 1, lca2
            
            return h1 + 1, node
        
        return helper(root)[1]
        

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type pair struct {
	first  *TreeNode
	second int
}

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
	var dfs func(root *TreeNode) pair
	dfs = func(root *TreeNode) pair {
		if root == nil {
			return pair{nil, 0}
		}
		l, r := dfs(root.Left), dfs(root.Right)
		d1, d2 := l.second, r.second
		if d1 > d2 {
			return pair{l.first, d1 + 1}
		}
		if d1 < d2 {
			return pair{r.first, d2 + 1}
		}
		return pair{root, d1 + 1}
	}
	return dfs(root).first
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function lcaDeepestLeaves(root: TreeNode | null): TreeNode | null {
    const dfs = (root: TreeNode | null): [TreeNode | null, number] => {
        if (root === null) {
            return [null, 0];
        }
        const [l, d1] = dfs(root.left);
        const [r, d2] = dfs(root.right);
        if (d1 > d2) {
            return [l, d1 + 1];
        }
        if (d1 < d2) {
            return [r, d2 + 1];
        }
        return [root, d1 + 1];
    };
    return dfs(root)[0];
}

1123 - Lowest Common Ancestor of Deepest Leaves

1123. Lowest Common Ancestor of Deepest Leaves (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1123. Lowest Common Ancestor of Deepest Leaves (Medium)

Solution 1.

All Problems

All Solutions