1123. Lowest Common Ancestor of Deepest Leaves #

Problem #

Given a rooted 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, and 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.

Example 1:

Input: root = [1,2,3]
Output: [1,2,3]
Explanation: 
The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1.
The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".

Example 2:

Input: root = [1,2,3,4]
Output: [4]

Example 3:

Input: root = [1,2,3,4,5]
Output: [2,4,5]

Constraints:

• The given tree will have between 1 and 1000 nodes.
• Each node of the tree will have a distinct value between 1 and 1000.

Problem Summary #

Given a rooted binary tree, find the lowest common ancestor of its deepest leaf nodes.

Recall that:

• A leaf node is a node in a binary tree that has no child nodes
• The depth of the root node of the tree is 0; if the depth of a node is d, then the depth of each of its child nodes is d+1
• If we assume A is the lowest common ancestor of a set of nodes S, then every node in S is in the subtree rooted at A, and A’s depth is the maximum possible value under this condition.  

Notes:

• The given tree will have 1 to 1000 nodes.
• The value of each node in the tree is between 1 and 1000.

Solution Approach #

• Given a tree, find the lowest common ancestor LCA of the deepest leaf nodes.
• The idea for this problem is relatively straightforward. First traverse to find the deepest leaf nodes. If the depths of the deepest leaf nodes in the left and right subtrees are the same, then the current node is their lowest common ancestor. If the maximum depths of the left and right subtrees are not equal, then continue recursively downward to find the LCA that satisfies the problem requirements. If the deepest leaf node has no sibling, then the common parent node is the leaf itself; otherwise, return its LCA.
• There are several special test cases; see the test file. The special point is the case where the deepest leaf node has no sibling node.

Code #

package leetcode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lcaDeepestLeaves(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	lca, maxLevel := &TreeNode{}, 0
	lcaDeepestLeavesDFS(&lca, &maxLevel, 0, root)
	return lca
}

func lcaDeepestLeavesDFS(lca **TreeNode, maxLevel *int, depth int, root *TreeNode) int {
	*maxLevel = max(*maxLevel, depth)
	if root == nil {
		return depth
	}
	depthLeft := lcaDeepestLeavesDFS(lca, maxLevel, depth+1, root.Left)
	depthRight := lcaDeepestLeavesDFS(lca, maxLevel, depth+1, root.Right)
	if depthLeft == *maxLevel && depthRight == *maxLevel {
		*lca = root
	}
	return max(depthLeft, depthRight)
}