Breaking a problem into sub-problems
This is a problem that seems to be suitable for breaking into three clear parts https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
There are three distinct parts of the problem:
1) Map each unique number to its corresponding node
2) Then, for each path in the tree, build a map <path len, path>. You will need to encode the path somehow (use your favorite encoder)
3) Now, do a linear search of all the max paths, looking for the first diff. Keep track of the latest common number, because that's what you'll return
Put it all together, works. Cheers, ACC.
public class Solution
{
public TreeNode LcaDeepestLeaves(TreeNode root)
{
//Map numbers to nodes
Hashtable numberToNode = new Hashtable();
MapNumberToNode(root, numberToNode);
//Max paths
Hashtable mapPath = new Hashtable();
int max = 0;
MapPaths(root, "", 0, mapPath, ref max);
//LCA number
int lcaNumber = LcaGivenPaths((List<string>)mapPath[max]);
return (TreeNode)numberToNode[lcaNumber];
}
private int LcaGivenPaths(List<string> paths)
{
int maxLen = 0;
for (int i = 0; i < paths.Count; i++)
{
maxLen = Math.Max(maxLen, paths[i].Length);
}
int previousNumber = 0;
int currentNumber = 0;
for (int i = 0; i < maxLen; i++)
{
bool foundDiff = false;
char c = '*';
for (int j = 0; j < paths.Count; j++)
{
if (i < paths[j].Length)
{
if (c == '*')
{
c = paths[j][i];
}
else
{
if (paths[j][i] != c)
{
foundDiff = true;
break;
}
}
}
}
if (foundDiff)
{
return previousNumber;
}
else
{
if (c == '@')
{
previousNumber = currentNumber;
currentNumber = 0;
}
else
{
currentNumber = 10 * currentNumber + (int)(c - '0');
}
}
}
return currentNumber;
}
private void MapPaths(TreeNode node, string path, int count, Hashtable mapPath, ref int max)
{
if (node == null) return;
if (node.left == null && node.right == null)
{
count++;
max = Math.Max(max, count);
path += node.val.ToString();
if (!mapPath.ContainsKey(count))
{
List<string> list = new List<string>();
list.Add(path);
mapPath.Add(count, list);
}
else
{
List<string> list = (List<string>)mapPath[count];
list.Add(path);
}
return;
}
if (node.left != null)
{
MapPaths(node.left, path + node.val.ToString() + "@", count + 1, mapPath, ref max);
}
if (node.right != null)
{
MapPaths(node.right, path + node.val.ToString() + "@", count + 1, mapPath, ref max);
}
}
private void MapNumberToNode(TreeNode node, Hashtable numberToNode)
{
if (node == null) return;
numberToNode.Add(node.val, node);
MapNumberToNode(node.left, numberToNode);
MapNumberToNode(node.right, numberToNode);
}
}
1123. Lowest Common Ancestor of Deepest Leaves
Medium
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 isd+1. - The lowest common ancestor of a set
Sof nodes is the nodeAwith the largest depth such that every node in S is in the subtree with rootA.
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.
There are three distinct parts of the problem:
1) Map each unique number to its corresponding node
2) Then, for each path in the tree, build a map <path len, path>. You will need to encode the path somehow (use your favorite encoder)
3) Now, do a linear search of all the max paths, looking for the first diff. Keep track of the latest common number, because that's what you'll return
Put it all together, works. Cheers, ACC.
public class Solution
{
public TreeNode LcaDeepestLeaves(TreeNode root)
{
//Map numbers to nodes
Hashtable numberToNode = new Hashtable();
MapNumberToNode(root, numberToNode);
//Max paths
Hashtable mapPath = new Hashtable();
int max = 0;
MapPaths(root, "", 0, mapPath, ref max);
//LCA number
int lcaNumber = LcaGivenPaths((List<string>)mapPath[max]);
return (TreeNode)numberToNode[lcaNumber];
}
private int LcaGivenPaths(List<string> paths)
{
int maxLen = 0;
for (int i = 0; i < paths.Count; i++)
{
maxLen = Math.Max(maxLen, paths[i].Length);
}
int previousNumber = 0;
int currentNumber = 0;
for (int i = 0; i < maxLen; i++)
{
bool foundDiff = false;
char c = '*';
for (int j = 0; j < paths.Count; j++)
{
if (i < paths[j].Length)
{
if (c == '*')
{
c = paths[j][i];
}
else
{
if (paths[j][i] != c)
{
foundDiff = true;
break;
}
}
}
}
if (foundDiff)
{
return previousNumber;
}
else
{
if (c == '@')
{
previousNumber = currentNumber;
currentNumber = 0;
}
else
{
currentNumber = 10 * currentNumber + (int)(c - '0');
}
}
}
return currentNumber;
}
private void MapPaths(TreeNode node, string path, int count, Hashtable mapPath, ref int max)
{
if (node == null) return;
if (node.left == null && node.right == null)
{
count++;
max = Math.Max(max, count);
path += node.val.ToString();
if (!mapPath.ContainsKey(count))
{
List<string> list = new List<string>();
list.Add(path);
mapPath.Add(count, list);
}
else
{
List<string> list = (List<string>)mapPath[count];
list.Add(path);
}
return;
}
if (node.left != null)
{
MapPaths(node.left, path + node.val.ToString() + "@", count + 1, mapPath, ref max);
}
if (node.right != null)
{
MapPaths(node.right, path + node.val.ToString() + "@", count + 1, mapPath, ref max);
}
}
private void MapNumberToNode(TreeNode node, Hashtable numberToNode)
{
if (node == null) return;
numberToNode.Add(node.val, node);
MapNumberToNode(node.left, numberToNode);
MapNumberToNode(node.right, numberToNode);
}
}
Comments
Post a Comment
[γγ¬γΌγ ]