[LeetCode] 742. Closest Leaf in a Binary Tree

 Problem : https://leetcode.com/problems/closest-leaf-in-a-binary-tree/

Because the goal is to find the nearest leaf node,  we use postorder to keep the shortest path to a leaf in left sub-tree or right sub-tree. 

If current node's value == k,  we use the shorter path from left or right sub-tree as the potential result. 

If k does not exist in either left sub-tree or right sub-tree, we only keep the shorter path

If k exists in left sub-tree, we consider path-to-value-k-in-left-sub-tree + shortest-path-to-leaf-in-right-sub-tree as potential result.

Similar procedure when k exists in right sub-tree.

This problem cannot solve by preorder traversal, because it cannot locate the lowest common ancestor with preorder traversal. 

Lesson learned:

- Postorder is useful we need to build path from leaf. 

- On each node, we can build a path by connecting path from left tree and path from right tree.

- We can return as much info as we need in postorder traversal.

# 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 findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:
        self.result = None
        
        def postorder(node):
            if not node.left and not node.right:
                if node.val == k:
                    self.result = (0, k)
                    
                return (1, node.val == k, node.val)
            
            leftDepth, leftHasK, leftLeaf = postorder(node.left) if node.left else (1000, False, -1)
            rightDepth, rightHasK, rightLeaf = postorder(node.right) if node.right else (1000, False, -1)
            
            
            if node.val == k:
                if leftDepth < rightDepth:
                    self.result = (leftDepth, leftLeaf)
                    return (1, True, -1)
                else:
                    self.result = (rightDepth, rightLeaf)
                    return (1, True, -1)
            elif leftHasK:
                if leftDepth + rightDepth < self.result[0]:
                    self.result = ((leftDepth + rightDepth), rightLeaf)

                return (leftDepth+1, True, -1)
            elif rightHasK:
                if rightDepth + leftDepth < self.result[0]:
                    self.result = ((rightDepth + leftDepth), leftLeaf)

                return (rightDepth+1, True, -1)
            else:
                if leftDepth < rightDepth:
                    return (leftDepth+1, False, leftLeaf)

                return (rightDepth+1, False, rightLeaf)
            
        
        postorder(root)
        
        return self.result[1]