Leetcode discuss: 1123. Lowest Common Ancestor of Deepest Leaves

 Here is the link. 

Second practice - C# - Height of Tree - Map - Array

Dec. 29, 2020
Introduction
It is easy to calculate the height of tree, and since all nodes in the tree have unique value, it is also practical to save all node's parent in an integer array, and also define a hashmap to map integer value to TreeNode.

My solution
I wrote a solution to calculate the height of tree, and then record each node's parent value in an integer array, and also a hashmap to map value to TreeNode.

For all leaf nodes, it is easy to determine by the height of node. Save all leaf nodes into a hashset. Next it is to find lowest common ancestor based on hashset.

Since all leaf nodes have same height, it is easy to go up one level, if there is only one parent, then it is LCA. Otherwise continue one more level up.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
     public TreeNode LcaDeepestLeaves(TreeNode root)
        {
            if (root == null)
                return null;

            var height = calculateHeightOfTree(root);

            var map = new Dictionary<int, TreeNode>();

            var leafNodes = new HashSet<int>();
            var parents = new int[1001];
            for (int i = 0; i < 1001; i++)
            {
                parents[i] = -1;
            }

            runPostOrder(map, null, root, 0, leafNodes, parents, height);                  

            while (leafNodes.Count > 1)
            {
                var parentNodes = new HashSet<int>(); 

                var list = leafNodes.ToList();  
                foreach(var item in list)
                {
                    parentNodes.Add(parents[item]); 
                }

                // next iteration
                leafNodes = parentNodes;
            }
            
            return map[leafNodes.ToList()[0]];            
        }

        private static void runPostOrder(Dictionary<int, TreeNode> map, TreeNode parent, TreeNode root, 
            int level, HashSet<int> leafNodes, int[] parents, int height)
        {
            if (root == null)
                return;

            map.Add(root.val, root);

            if (parent != null)
            {
                parents[root.val] = parent.val;
            }

            if (level + 1 == height)
            {
                leafNodes.Add(root.val);
            }

            runPostOrder(map, root, root.left,  level + 1, leafNodes, parents, height);
            runPostOrder(map, root, root.right, level + 1, leafNodes, parents, height);
        }

        private static int calculateHeightOfTree(TreeNode root)
        {
            if (root == null)
                return 0;

            return Math.Max(calculateHeightOfTree(root.left) + 1, calculateHeightOfTree(root.right) + 1);
        }
}